2

假设我有一个列表，该列表priority按其元素的属性排序，该属性是一个数字。我知道priority列表中每个成员的值，但我想将一个元素移动到特定索引。priority是否可以仅通过修改我要移动的元素来做到这一点？

priority不需要是整数。任何算法都可以用来确定priority元素需要是什么，但priority必须是唯一的。

我认为priority在所需索引之前和之后获取元素，但我不知道如何在它们之间选择一个最终不会导致重复的数字。如果我只是在之前的元素中添加一些给定的值（整数或小数），我最终会得到与之后的元素相同的值。调用random()两者之间的范围会起作用，但这似乎是一种非常迂回的做事方式。

如果这种操作有名字，我也有兴趣学习一下。

4

2 回答 2

1

值 m = (upper+lower)/2 始终位于两个值的中间。

关于编号的进一步阅读，我参考了一个讲座： http ://www.cs.uni-paderborn.de/fachgebiete/ag-boettcher/lehre/ss2012/dbis-2/download.html

于 2013-11-05T17:52:20.730 回答
1

(upper+lower)/2 怎么样？

扩展@msander 的答案，您可以使用字母数字优先级来确保您始终拥有“中间”优先级来分配。如果你需要分配许多优先级，两个连续优先级之间的距离会越来越小，最终会失去精度，你会得到类似 ((upper + lower)/2 === lower) 的东西。

如果您更改获得中间优先级的方式，则可以使用字符串（不损失精度）而不是实际数字。例如，如果您的优先级是类似字符串的数字（由 0、1、2、3、4、5、6、7、8、9 组成的字符串）：

['1', '3', '4']

在 1 和 3 之间移动 4 将导致：['1', '2', '3']

在 2 和 1 之间移动 3 将导致：['1', '15', '2']

在 1 和 15 之间移动 2 将导致：['1', '12', '15']

您需要注意的是如何比较优先级（String.prototype.localeCompare）。

同样，只有当您预计会遇到精度损失问题时，此解决方案才值得麻烦。

编辑（添加了一个计算优先级的函数）：

免责声明：该代码出乎意料地难以理解。如果有人有更好的想法，请随意加入。如果您只使用二进制字符串（仅包含 0 和 1 的字符串），编写起来会容易得多。

function getMiddlePriority(p1, p2) {
  var i=0,result = '';

  // The identical digits need to be in the result
  while ((p1[i] || '0') === (p2[i] || '0')) {
    result += p1[i++] || '0';
  }

  // First different digit p1[i] !== p2[i]

  // if the digits are far enough apart, there is a number between them
  if ((p2[i]||0) - (p1[i]||0) > 1) {
    return result + Math.floor(((+p2[i]||0) + (+p1[i]||0))/2);
  }

  // p2[i] === p1[i]+1

  // Digits are close, need to parse some more digits to get a number between
  var first = i++;
  var k = 0;
  while ((p1[i] === '9') && ((p2[i]||'0') === '0')) {
    i++; 
    k++;
  }


  // p[i] is not 9 or p2[i] is not 0/undefined
  if (p1[i] === '9') {
    result += (p2[first]||'0')  + repeat('0', k);
    result += p2[i] === '1' ? '05' : Math.floor(p2[i]/2);
  } else {
    result += (p1[first]||'0') + repeat('9', k);
    result += Math.floor((10 + (+p1[i] || 0))/2);
  } 

  return result;
}


function repeat(character, count) {
  var s = '';
  while (count--) s+= character;
  return s;
}


console.clear();
console.log('Expected 2 Got ' + getMiddlePriority('1', '3'));
console.log('Expected 25 Got ' + getMiddlePriority('2', '3'));
console.log('Expected 22 Got ' + getMiddlePriority('2', '25'));
console.log('Expected 21 Got ' + getMiddlePriority('2', '22'));
console.log('Expected 205 Got ' + getMiddlePriority('2', '21'));
console.log('Expected 202 Got ' + getMiddlePriority('2', '205'));
console.log('Expected 215 Got ' + getMiddlePriority('21', '22'));
console.log('Expected 1055 Got ' + getMiddlePriority('105', '106'));
console.log('Expected 10995 Got ' + getMiddlePriority('1099', '11'));
console.log('Expected 1105 Got ' + getMiddlePriority('1099', '111'));

字符串优先级的替代方法是使用数字优先级，并且每隔一段时间（何时(upper+lower)/2 === lower || (upper+lower)/2 === upper）重新分配优先级。当然这不适合这个问题，因为对于 N 次重新排序，您不会进行 1 次更新，而是进行1+ N/S更新，其中 S 是您在用完可用优先级之前可以进行的更新量。至少这是一个正确的解决方案（优先级总是唯一的）。

于 2013-11-05T17:57:02.560 回答