0

我有一个数组，其中一些元素是“重复”，我想删除数组中的重复。

所以比如左边的列表（数组）变成右边的数组：

Ingredients:             Ingredients:
Apples                   Apples
Apples                   Oranges
Oranges                  Bananas
Oranges
Oranges
Bananas

这样做的好算法是什么？

现在这就是我的伪代码的样子：

for each element in ingredients (counter j)
     for each element-below-current-element (counter k)
         if ingredients[i] == element-below-current-element[j]
             splice (delete) ingredients[i]

但现在的问题是我注意到如果原始列表有奇数个元素，那么我可能会得到这样的结果：

Ingredients:             Ingredients:
Apples                   Apples
Oranges                  Oranges
Oranges                  Oranges
Oranges                  Bananas
Bananas

一切正常，除了我可能会得到一种成分的双倍。

这是我的实际代码实现，在javascript中并带有一些角度元素（例如 $scope），尽管它并不重要。

    for(var j = 0; j < $scope.groceryList.length; j++){
        for(var k = j+1; k < $scope.groceryList.length; k++){ // for each of elements below current element (j)
            if ( $scope.groceryList[j].name == $scope.groceryList[k].name){
                $scope.groceryList.splice(k, 1);
                }
            }
    }

现在让我明白的是，每当你删除一个数组元素时，数组长度是如何减少的，​​这会导致你的计数器在下一次迭代中向前跳跃一个元素等等......

4

8 回答 8

4

Underscore.js是我推荐的用于在 JavaScript 中进行所有数组处理的工具（以及，对于，只是，就像，一切。太棒了。）

碰巧它的uniq方法将完全满足您的需求。

var myArray = ["Apples","Oranges","Oranges","Grapes","Apples"];
_.uniq(myArray);
//returns ["Apples","Oranges","Grapes"]
于 2013-07-29T20:45:25.657 回答
2

在这种情况下，您通常不能for为内部循环使用循环。while不过效果很好：

for(var j = 0; j < $scope.groceryList.length; j++){
    var k = j+1;
    while(k < $scope.groceryList.length){ // each of elements below current element (j)
        if ( $scope.groceryList[j].name == $scope.groceryList[k].name){
            $scope.groceryList.splice(k, 1);
            }
        else {
            ++k;
            }
        }
}

如果你拼接，不要增加k. 如果你不这样做，做。

（我希望我的缩进是正确的，这不是我习惯的风格。）

于 2013-07-29T20:41:25.537 回答
1

我只是对其进行排序，然后像这样比较....

var arr = ["Apples","Oranges","Oranges","Grapes","Apples"];
 var sorted_arr = arr.sort(); 

  var results = [];
  for (var i = 0; i < arr.length - 1; i++) {
    if (sorted_arr[i + 1] == sorted_arr[i]) {
    results.push(sorted_arr[i]);
  }
 }

alert(results);
于 2013-07-29T20:41:47.037 回答
1

线性时间、常数空间算法：

  1. 有 2 个索引（一个快一个慢），都从零开始
  2. 递增两者，直到前一个元素与当前元素相同
  3. 增加快的，直到你找到一个不同的元素
  4. 将慢速索引处的元素设置为快速索引处的元素
  5. 增加两者
  6. 增加快速的，直到它与替换元素不同
  7. 从 4 开始重复，直到快速完成。
  8. 将列表缩短到较短的

不，我不能给你 JavaScript。

例子：

输入：

Ingredients, Apples, Apples, Oranges, Oranges, Oranges, Bananas

有 2 个索引（一个快一个慢），都从零开始

   fast
   slow
     V
Ingredients, Apples, Apples, Oranges, Oranges, Oranges, Bananas

递增两者，直到我们前一个元素与当前元素相同。

                     fast
                     slow
                       V
Ingredients, Apples, Apples, Oranges, Oranges, Oranges, Bananas

快速增加直到它不同。

                     slow     fast
                       V        V
Ingredients, Apples, Apples, Oranges, Oranges, Oranges, Bananas

将慢速元素设置为快速元素。

                     slow      fast
                       V         V
Ingredients, Apples, Oranges, Oranges, Oranges, Oranges, Bananas

两者都增加。

                               slow     fast
                                 V        V
Ingredients, Apples, Oranges, Oranges, Oranges, Oranges, Bananas

增加快速的，直到它与替换元素不同（橙子）

                               slow                       fast
                                 V                          V
Ingredients, Apples, Oranges, Oranges, Oranges, Oranges, Bananas

将慢速元素设置为快速元素。

                               slow                       fast
                                 V                          V
Ingredients, Apples, Oranges, Bananas, Oranges, Oranges, Bananas

两者都增加。

                                        slow                  fast
                                          V                     V
Ingredients, Apples, Oranges, Bananas, Oranges, Oranges, Bananas

到达终点。

将列表缩短至缓慢。

Ingredients, Apples, Oranges, Bananas
于 2013-07-30T00:23:01.843 回答
1

我最喜欢的方法是使用数组方法来保存代码：

arr1=[
    "Apples",
    "Apples",
    "Oranges",
    "Oranges",
    "Oranges",
    "Bananas"
];


var unq= arr1.filter(function unq(a,b,c){return c.indexOf(a)===b;});

alert(unq); // shows "Apples,Oranges,Bananas"

没有变量，没有工件，只有逻辑和结果。

编辑：更改为仅使用一个重复数组。如果您想从另一个数组中筛选出一个数组，只需将上面的“c.indexOf”更改为数组的 var 名称。

我更喜欢打破 unq 函数，这样我就可以从任何地方调用 .filter(unq) 来获得一个唯一的数组......

于 2013-07-29T20:49:23.613 回答
1

此代码是最简单的解决方案，但需要双倍的内存量 - 对于您示例中的小数据集来说不是问题。

Array.prototype.filterDuplicates = function () {
    var filtered = [];
    for (var i = 0; i < this.length; i++)
        if (filtered.indexOf(this[i]) == -1)
            filtered.push(this[i]);
    return filtered;
}
于 2013-07-29T20:46:45.770 回答
0

http://jsfiddle.net/XYsUm/

var ingredients = [
    "Apples",
    "Apples",
    "Oranges",
    "Oranges",
    "Oranges",
    "Bananas"
];

var uniqIngredients = {};

for (i in ingredients) {
    uniqIngredients[ingredients[i]] = true;
}

ingredients = [];

for (i in uniqIngredients) {
    ingredients.push(i);
}
于 2013-07-30T08:32:45.067 回答
0

只需使用关联数组进行存在性检查：

var exists = {}, i;
for (i = 0; i < arr.length; i += 1) {
    if (exists[arr[i]]) {
        arr.splice(i, 1);
        i--;
    } else {
        exists[arr[i]] = true;
    }
}
// arr should now have no dupes
于 2013-07-29T20:45:24.407 回答