已排序数组中删除重复项

8

提醒一下,这个问题是关于如何在已排序的数组中删除重复项。相比于未排序的数组,可以应用非常快速的算法来移除重复项。

  • 如果您已经知道如何删除已排序数组中的重复项,则可以跳过此部分。

示例:

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];

*排序可以是升序或降序,也可以按其他奇怪的方法进行,但重要的是每个重复的项都在一起。

我们停在array.length-1,因为没有东西可以检查了。

然后我们添加最后一个元素,而不考虑任何因素,因为:

情况A:

... ,9,9,9] //我们在最后一个元素左边有重复项

情况B:

... ,7,9,10] //我们在最后一个元素的左边没有重复项

如果你真正理解现在正在发生的事情,你会知道我们在情况A中并没有添加任何9。因此,由于这个原因,我们想无论是情况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]);

我真的很迷茫,需要帮助。


你想要什么样的行为?你只是想忽略不存在的数组部分,还是怎样? - Peter Olson
@peter 我想删除重复项,即使它们之间有未定义的内容。 - ajax333221
我认为你应该将初始数组打包到一个临时数组中(删除未定义的值),并使用该数组进行重复检查。 - Gabriele Petrioli
15个回答

13

使用.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]);

个人建议不要使用其他答案中所提到的如此复杂的解决方案。


3
这是一个简洁表述:

这是一个一句话说明:

uniquify( myArray.filter(function(x){return true}) )

如果您还没有编写uniquify(用于删除重复项的函数),您也可以使用以下两行代码:

var newArray = [];
myArray.forEach(function(x) {
    if (newArray.length==0 || newArray.slice(-1)[0]!==x)
        newArray.push(x)
})

解释:

var a=[];
a[0]=1; a[1]=undefined; a[2]=undefined;
a[10]=2; a[11]=2;

据OP所说,即使a.length==12,数组仍然具有“五个元素”。尽管a[4]===undefined,根据他的定义,它不是数组的一个元素,不应该被包括在内。 a.filter(function(x){return true})将把上述数组转换为[1, undefined, undefined, 2, 2]
编辑:最初使用了.reduce()而非.forEach()编写,但.forEach()版本更不可能在javascript的低效实现中引入垃圾回收器和传值问题。
对于那些担心与6年前的MIE8浏览器兼容性的人,可以在https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/forEach中包含代码。然而,如果一个人很关心浏览器兼容性,就应该通过像GWT这样的跨编译器来编程。如果你使用jQuery,你也可以只用几个额外的字符重写上面的代码,如$.forEach(array, ...)

请注意,这需要支持“Array.reduce”的现代浏览器。例如,在<=IE8上将无法工作。 - Peter Olson
感谢您的关注。然而,IE8发布已经超过半个十年了。它发布的操作系统已经被微软正式终止支持多年。即使在Windows 7上,根据http://www.computerworld.com/s/article/9215845/Microsoft_to_push_IE9_via_Windows_Update_next_week,微软也已经开始向仍在使用IE8的计算机提供弹出式下载(这是一年前的事情)。这已经成为ECMAScript 5标准自2009年以来的内容。如果没有Array.map()/.filter()/.forEach()编程将非常痛苦,让人想起C语言。 - ninjagecko
我不是在谈论那些未定义的,我是在谈论那些在这里不会被警告的未定义变量 for(var i=0;i<array.length;i++){if(i in array){alert(array[i]);}} - ajax333221
@ninjagecko,2009年并不是“半个多十年前”,而且IE<=8的市场份额仍然是IE9的两倍以上,所以我认为这仍然是一个有效的问题。 - Peter Olson
IE8是在2009年发布的第一个非测试版,截至2011年12月仍占有22%的市场份额,但如果您愿意忽略五分之一的潜在用户,那就继续使用吧。请注意,许多人由于工作场所的IT政策限制(例如,在我目前的工作场所,我们仍在使用XP和IE_7_),无法使用IE9。 - nnnnnn
@PeterOlson:啊,抱歉,我是指2008年,也就是4年前。我会承认市场份额的观点,但要注意的是,这是否是一个问题取决于你的受众。这些计算机是否真的有人在使用,以及人类是否会访问正在构建的网站或者说相同的语言,只能通过收集正在构建的网站的统计数据来衡量。很明显,仍有5-10%的互联网用户在使用MIE8。可以通过使用像jQuery/GWT或上面提到的链接这样的库来满足这些用户的需求,而不会变得疯狂,或者减缓Web标准的发展。 - ninjagecko

3

首先,我不确定你的原始代码是否正确。在原始列表为空时,您尝试推送最后一个元素,这可能导致代码无法正常工作。更好的写法可能是:

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]

我喜欢这种逻辑,标记第一个元素是否比检查数组长度为0更好。 - ajax333221

2
也许像这样:

可能会是这样的:

var out = [],
    prev;

for(var i = 0; i < arr.length; i++) {
   if (!(i in arr))
      continue;

   if (arr[i] !== prev || out.length === 0) {
      out.push(arr[i]);
      prev = arr[i];
   }
}
out.length 的检查是为了允许第一个定义的数组元素在 prev 初始状态下也为 undefined 时具有该值。
请注意,与您原来的算法不同,如果 arr 为空,则不会将未定义的值推送到您的 out 数组中。
或者,如果您的浏览器版本足够新,您可以使用 Array.forEach() 方法,它只迭代已分配值的数组元素。

好的,我只需要将等号改为 arr[i] !== prevout.length == 0。(我想这才是你一开始的意思) - ajax333221
谢谢。是的,我应该说arr[i] !== prev - 很好的发现 - 我已经更新了我的答案来反映这一点。但是我确实意味着 out.length === 0(数组长度始终是数字)。 - nnnnnn
数组长度始终是数字,那么为什么要使用 === - ajax333221
为什么不使用 ===?我只在想要比较可能被强制转换为相同类型和值的不同类型操作数时才使用 == - nnnnnn
当我认为强制转换可能会产生意外结果时,我只使用 ===!==。如果我确切地知道我正在处理什么,并且 ==!= 永远不会让我陷入问题中,我会使用它们并节省一个字符。 - ajax333221

1

我认为这就是你想要的。这是一个相当简单的算法。

var out = [], previous;
for(var i = 0; i < arr.length; i++) {
  var current = arr[i];
  if(!(i in arr)) continue;
  if(current !== previous) out.push(current);
  previous = arr[i];
}

这将在O(N)时间内运行。


这不符合原帖的要求,即区分已被赋予 undefined 值的数组元素(需要保留)和从未赋值的索引。 - nnnnnn
@nnnnnn 我不确定是否理解,我问他想要什么行为,他只是说尽管在重复值之间有未定义值也要删除重复项。他不希望对数组中在重复值之间被分配为 'undefined' 的值进行删除吗? - Peter Olson
考虑以下代码:var arr=[]; arr[5]=1; arr[9]=undefined; arr[11]=undefined; arr[13]=3 - 在这段代码之后,arr.length为14,但索引位置0-4、6-8、10和12从未被赋值,而这些是OP想要跳过的。索引9和11已经明确地分配了undefined,不应该被跳过。OP在帖子中间的“问题”标题下提到了这一点,但解释得不是很清楚。然后,旨在澄清的评论实际上使其更加不清楚(所以也许我误解了)。 - nnnnnn
@PeterOlson 我的意思是指不包含 undefined 值的未定义变量。换句话说,它们不会出现在这里 for(i=0;i<array.length;i++){if(i in array){alert(array[i]);}} - ajax333221
是的,这就是我在寻找的。非常抱歉我的不够清晰的指示导致你在“nnnnnn”之后才回答它。我对此发生的事情负全部责任。 - ajax333221

1

一种明确的方法是打包数组(删除undefined值),然后在其上使用现有算法来处理重复项。

function pack(_array){
    var temp = [],
        undefined;
    for (i=0, len = _array.length; i< len; i++){
        if (_array[i] !== undefined){
            temp.push(_array[i]);
        }   
    }
    return temp;
}

“打包”这个想法也是我的第一反应,并且要点赞确保undefined确实是未定义的,但请注意,你的实现并不符合OP的要求,不能区分已分配了_值_为undefined的数组元素(需要保留)和从未被分配值的索引(需要跳过)。 - nnnnnn
@nnnnnn,嗯...有道理,尽管我不确定这是否确实是OP的关注点...我认为这只是一个解释,即值确实未定义...而不是他想要不同的处理方式。 - Gabriele Petrioli

1
一个非常简单的函数,输入数组必须是已排序的:
function removeDupes(arr) {
  var i = arr.length - 1;
  var o;
  var undefined = void 0;

  while (i > 0) {
    o = arr[i];

    // Remove elided or missing members, but not those with a 
    // value of undefined 
    if (o == arr[--i] || !(i in arr)) {
      arr.splice(i, 1);
    }
  }
  return arr;
}

这段代码可能可以更简洁,但可能会变得晦涩难懂。顺便提一下,输入数组被修改了,所以它不需要返回任何东西,但如果它返回一些东西的话可能更方便。

以下是一个正向循环版本:

function removeDupes2(arr) {
  var noDupes = [],
      o;

  for (var i=0, j=0, iLen=arr.length; i<iLen; i++) {
    o = arr[i];
    if (o != noDupes[j] && i in arr) {
       noDupes.push(o);
       j = noDupes.length - 1;
    }
  }
  return noDupes;
}

PS

应该在任何支持JavaScript的浏览器上工作,无需任何额外的库或补丁。


它会删除包含“undefined”值的两个项目以及伪“undefined”项目。(我只想删除伪造的那些) - ajax333221
非常简单的编辑更改(已完成),尽管这是一个奇怪的要求。 - RobG

1

这个解决方案可以原地删除重复元素。不建议在函数式编程中使用。

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

const removeDuplicates = (nums) => {
  nums.forEach((element, idx) => {
    nums.splice(idx, nums.lastIndexOf(element) - idx)
  })
}

removeDuplicates(arr)

console.log(arr);


0

我相信你想要实现的并不完全可能,但我可能错了。

这就像是那些经典的计算机科学问题之一,比如一个村庄里的理发师只给那些不为自己刮胡子的人剃须。如果将数组索引项的值设置为undefined,它并不是真正的undefined。不是这样吗?只有在未初始化时,值才能为undefined

你应该检查的是一个值是否为nullundefined。如果是null或重复的值,则跳过该值,否则保留它。

如果你想跳过null值和重复值,那么下面的函数就可以解决问题。

function  removeDuplicateAndNull(array){

    if(array.length==0)
        return [];

    var processed = [], previous=array[0];
    processed.push(array[0]);

    for(var i = 1; i < array.length; i++) {

        var value = array[i];

        if( typeof value !== 'undefined' && value ==null) 
            continue;

        if(value !== previous || typeof value === 'undefined')
            processed.push(value);

        previous = array[i];
    }
    return processed;
}

测试用例:

  1. array=[,5,5,6,null,7,7] output =[ ,5,6,7]

  2. array=[ 5,5,,6,null,,7,7] output=[5,,6,,7]

  3. array=[7,7,,] output=[7,]

但即使使用这个函数也有一个注意事项。如果您检查第三个测试,输出是[7,]而不是[7,,]! 如果您检查输入和输出数组的长度,array.length=3,output.length=2。 这个注意事项不是由于函数本身,而是由于JavaScript本身。


已接受的答案可行,它过滤了未定义的值,但保留手动设置的未定义值。使用以下代码 -> var arr=[];arr[3]=1;arr[5]=undefined;arr[6]=undefined;arr[8]=true;arr[10]=true; 输出应为 1,,true - ajax333221

0
//sort the array
B.sort(function(a,b){ return a  - b});
//removing duplicate characters
    for(var i=0;i < B.length; i ++){
        if(B[i]==B[i + 1])
            B.splice(i,1)
    }

如果下一个索引中的元素与当前位置相同,则删除当前位置的元素。
splice(targetPosition,noOfElementsToBeRemoved)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接