去重算法，就地且稳定（JavaScript）

Question

今天在课堂上我们被要求编写一个算法。

给定一个数组，删除重复的值：

• 它应该是稳定的，并且不必使用内部循环。
• 应尽可能原地完成
• 不使用内置函数（我只能使用 .push）

经过一番奋斗，这就是我想出来的。

function remove_dupes(arr){
  var seen = {};
  var count = 0;

  for( var i = 0; i < arr.length - count ; i++) {
    arr[i] = arr[i+count];

    if( seen[arr[i]] ) {
      count++;
      arr[i] = arr[i+count];
      i--;
    }

    seen[arr[i]] = true;
  }

  arr.length = arr.length - count;
}

工作中的JSBin

这里有一些重复的代码，我感觉使用 i-- 可能不是最好的方法。

有没有什么方法可以改进这段代码（不使用内置函数）？

- ahnkee

---

我实际上认为这段代码写得相当不错。很难编写出与处理不可变对象的解决方案一样整洁的原地代码。 - undefined

感谢您的反馈。我在课程中还处于早期阶段，所以他们正在尽可能地向我们灌输基础知识和基本原理。我的直觉还没有发展到能够独立判断某个解决方案是否最优的程度，所以Stack Overflow对我来说是一个很大的帮助。 - undefined

Answer 1

最后，我认为我已经按照您的要求完成了，并且没有创建新的数组：

function remove_dupes(arr){
  var seen = {};
  
  var k = 0;
  for( var i=0; i<arr.length ;i++) {
    if( !seen[arr[i]] ) {
      arr[k++] = arr[i];
      seen[arr[i]] = 'seen';
    }
  }
  
  arr.length = k;
}


var x = [ 1, 2, 1, 4, 5, 3, 'dojo', 4, 6, 6, 7, 7, 6, 7, 5, 6, 6, 6, 6, 7, 'dojo', 11 ];
remove_dupes(x);


document.write(x);

希望这能帮到你。

- user4227915

---

我认为这个解决方案很棒，我打算接受它作为答案。 - undefined

arr.length = k;是一个不错的技巧，但需要有文档说明。 - undefined

Answer 2

这对我来说似乎是一个更简单的解决方案：

function remove_dupes(arr){
  var seen = {};
  var dupes_removed = [];

  for( var i = 0; i < arr.length; i++) {
    if (!seen[arr[i]]) {
      dupes_removed.push(arr[i]);
      seen[arr[i]] = true;
    }
  }

  return dupes_removed;
}

这个程序的时间复杂度介于O(n)和O(nlogn)之间（因为JS哈希查找的时间复杂度在O(1)和O(logn)之间）。这还保证结果是稳定的。迄今为止，其他解决方案要么时间复杂度为O(n^2)，要么不稳定。

- Dev Chakraborty

---

然而，这个解决方案并不符合问题的要求。它会创建一个新的数组。 - undefined

是的，就像@ivern说的那样。我喜欢这段代码的简洁性，但是在课堂上我们被要求不要创建一个新的数组。你能否修改你的解决方案，尽可能地在原地进行操作？ - undefined

Answer 3

你可以使用indexOf来判断该值是否存在于arr中，然后将其推入一个新的数组中。

function remove_dupes(arr){
  var newArr = [];
  for( var i = 0; i < arr.length; i++){ 
    if(newArr.indexOf(arr[i]) === -1){
      newArr.push(arr[i]);
    }
  }
  
  return newArr;
}

var myArr = [2,4,2,4,6,6,6,2,2,1,10,33,3,4,4,4];

console.log(remove_dupes(myArr));

- Joy Biswas

---

很干净的解决方案，但是我被要求不能创建一个数组来返回，也不能使用像indexOf这样的函数。我尽量要在原地完成它。 - undefined

Answer 4

你可以使用 Array.prototype.splice 来直接改变数组（fiddle - 查看控制台）：

var arr = [1, 54, 5, 3, 1, 5, 20, 1, 54, 54];

var seen = {};

var length = arr.length;

var i = 0;

while (i < length) {
    if (seen[arr[i]] !== undefined) {
        arr.splice(i, 1);
        length--;
    } else {
        seen[arr[i]] = true;
    }

    i++;
}

console.log(arr);

这是O(n^2)的，因为splice是O(n)，而我们要迭代n个元素。

- Ori Drori

---

我最初使用splice做了类似的事情，但我的导师向我提出了挑战，要求我不使用任何内置函数，所以我被迫选择了另一种方法。 - undefined

没有问题，只需将其添加到问题中。 - undefined

我在问题的最后一行提到了这一点，但是你说得对，应该更加明显。我会进行编辑。 - undefined

不好意思，我的错。确实有助于在问题之前更清楚地表达，并将所有要求放在一个地方。我还在学习如何使用SO，感谢您的反馈。 - undefined

Answer 5

这是我在我的JS数组子类中使用的一种简洁的解决方案：

if ( !Array.unique )
{
    Array.prototype.unique = function()
    {
        var tmp = {}, out = [], _i, _n ;
        for( _i = 0, _n = this.length; _i < _n; ++_i )
        if(!tmp[this[_i]]) { tmp[this[_i]] = true; out.push(this[_i]); }
        return out;
    }
}

- Sandro Rosa

---

这是在创建一个新的数组并返回它，对吗？从我的理解来看，这不是原地操作。 - undefined

你的意思是要在“原地”使用“相同的工作数组”吗？ 如果是这样，您可能需要扫描每个元素，通过.indexOf检查数组，并通过.splice每次删除第一个索引元素，直到.indexOf不返回-1为止...这是基本的想法，已经在上面展示过了。 - undefined

正确。同一个数组。然而，正如我在问题中所述，我不应该使用任何内置函数，比如splice或indexOf。那是挑战的一部分。 - undefined

嗯，这听起来就像是一个练习题。不管怎样，如何在不“拼接”数组的情况下去除重复项呢？ - undefined

我采取的方法（以及我接受的答案的方法）基本上是将所有唯一元素移动到数组的前面，将重复元素移动到数组的末尾。通过计数器，您可以知道哪个索引将唯一元素和重复元素分开，所以只需在该点截断数组即可。 - undefined

你可能也想将这种方法与这里报告的方法进行基准测试，看看哪个运行得更快。你可能在编码方面很擅长，但如果它运行得更慢，那么你就错过了重点。所以首先生成一个包含1到10之间的10000个随机条目的数组。然后记录两种方法的unix时间消耗。 - undefined