删除排序数组上的重复项

Question

以防万一你错过了，问题是关于删除sorted数组上的重复项。可以应用非常快速的算法（与未排序的数组相比）来删除重复项。

• 如果您已经知道如何删除 SORTED 数组上的重复项，则可以跳过此步骤

例子：

var out=[];
for(var i=0,len=arr.length-1;i<len;i++){
    if(arr[i]!==arr[i+1]){
        out.push(arr[i]);
    }
}
out.push(arr[i]);

看到了吗，速度很快。我会尽力解释刚刚发生的事情。

排序后的数组 * 可能如下所示：

arr=[0,1,1,2,2,3,4,5,5,6,7,7,8,9,9,9];

*排序可以是 ASC 或 DESC，或者通过其他奇怪的方法，但重要的是每个重复的项目都是相邻的。

我们停下来是array.length-1因为我们没有任何东西可以检查

然后我们不管任何事情都添加了最后一个元素，因为：

案例一：

... ,9,9,9];//we have dup(s) on the left of the last element

案例B：

... ,7,9,10];//we don't have dup(s) on the left of the last element

如果您真的了解发生了什么，您就会知道我们没有9在案例 A 上添加任何内容。因此，无论我们是在案例 A 还是 B 上，我们都希望添加最后一个元素。

---

题：

这解释了，我想做同样的事情，但忽略以下undefined情况的价值：

var arr=[];arr[99]=1;//0 through 98 are undefined, but do NOT hold the undefined value

我想删除那些。如果我有一些实际undefined值，则不应删除这些值。

我糟糕的尝试是这样的：

var out=[];
for (var i=0,len=arr.length; i < len - 1;) {
  var x = false;
  var y = false;

  for (var j = i, jo; j < len - 1; j++) {
    if (j in arr) {
      x = true;
      jo = arr[j];
      i = j + 1;
      break;
    }
  }
  if (x == false) {
    break;
  }

  for (var u = i, yo; u < len - 1; u++) {
    if (u in arr) {
      y = true;
      yo = arr[u];
      i = u + 1;
      break;
    }
  }
  if (y == false) {
    out.push(jo);
    break;
  }

  if (jo !== yo) {
    out.push(jo);
  }
}
out.push(arr[len - 1]);

我真的很迷茫，任何帮助表示赞赏

Answer 1

使用 .filter() 的现代单行

arr.filter((e, i, a) => e !== a[i - 1]);

我对这里其他答案的复杂性感到非常惊讶，即使是那些使用 .filter()

即使使用没有箭头函数的老式 ES5 语法：

arr.filter(function (e, i, a) { return e !== a[i - 1] });

例子：

let a = [0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9];

let b = arr.filter((e, i, a) => e !== a[i - 1]);

console.log(b); // [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

如果您需要就地改变数组，则只需使用：

arr = arr.filter((e, i, a) => e !== a[i - 1]);

我个人建议不要使用像这里其他答案中的解决方案那样复杂的解决方案。

Answer 2

首先，我不完全确定您的原始代码是否正确。在我看来，当原始列表为空时，它可能无法正常工作，因为无论如何您都会尝试推送最后一个元素。可能更好地写成：

var out = [];
var len = arr.length - 1;
if (len >= 0) {
    for (var i = 0;i < len; i++) {
        if (arr[i] !== arr[i+1]) {
            out.push (arr[i]);
        }
    }
    out.push (arr[len]);
}

至于你的实际问题，我会用算法来回答这个问题，因为我不太了解 JavaScript，但在我看来，你只需记住最后传输的号码即可，例如：

# Set up output array.

out = []

# Set up flag indicating first entry, and value of last added entry.

first = true
last = 0

for i = 0 to arr.length-1:
    # Totally ignore undefined entries (however you define that).

    if arr[i] is defined:
        if first:
            # For first defined entry in list, add and store it, flag non-first.

            out.push (arr[i])
            last = arr[i]
            first = false
        else:
            # Otherwise only store if different to last (and save as well).

            if arr[i] != last:
                out.push (arr[i])
                last = arr[i]