For example: [8,2,2,5] => [8,2,5]

  • The array is not sorted.
  • Repeating items always go in a row.

I came up with a solution with two cycles and a second array. So I decided to ask if there is any more elegant solution.

  • Is the array sorted? You can use ready-made solutions (the same lodash, for example) - Alexey Ten
  • @AlexeyTen Sori for an unqualified example, no, the array is not sorted. - user208916
  • Is this a problem case not from the exam? - t1nk 1:51 pm
  • @ t1nk No, I'm working. - user208916

5 answers 5

Algorithm with linear asymptotics.

In this implementation, modifies the original array, but can be easily converted to create a new one.

 function doSmth(a) { for (var q=1, i=1; q<a.length; ++q) { if (a[q] !== a[q-1]) { a[i++] = a[q]; } } a.length = i; return a; }
  • cool, did not know that .length can be installed. Concise and effective! - Sergiks
  • @Sergiks And why set the length please explain? - user208916
  • one
    There are two pointers along the array: q (reads) and i (writes). When a series of repetitive values ​​begins, q goes forward. And i writes down one new value, trailing behind. As a result, everything to the left of i is unique values ​​one by one. Setting .length = i truncates the array so that only elements to the left of i remain. - Sergiks
  • @Sergiks And why use the prefix form of increment ++q in a loop? - user208916
  • @Khipster is here without a difference ++q or q++ . - Sergiks 5:52 pm

The short solution is:

 uniqueArray = a.filter(function(item, pos) { return a.indexOf(item) == pos; })

A little smarter can be this:

 function uniq(a) { var seen = {}; return a.filter(function(item) { return seen.hasOwnProperty(item) ? false : (seen[item] = true); }); }

Combining these two approaches:

 function uniq(a) { var prims = {"boolean":{}, "number":{}, "string":{}}, objs = []; return a.filter(function(item) { var type = typeof item; if(type in prims) return prims[type].hasOwnProperty(item) ? false : (prims[type][item] = true); else return objs.indexOf(item) >= 0 ? false : objs.push(item); }); }

The fastest solution (without function calls):

 function uniq_fast(a) { var seen = {}; var out = []; var len = a.length; var j = 0; for(var i = 0; i < len; i++) { var item = a[i]; if(seen[item] !== 1) { seen[item] = 1; out[j++] = item; } } return out; }

Source with all the details: https://stackoverflow.com/a/9229821/2707359

  • Cool, I have never thought of such a trick with filter and indexOf. 5+ And in my opinion this method will be not a bit slower than the last. - user208916
  • @Khipster It is only necessary to understand that these are the same two cycles. - Alexey Ten
  • @AlexeyTen Well and good. Arrays in theory are faster than objects. Therefore, I now doubt about the last fastest method where the object is used. - user208916
  • @AlexeyTen Check it out I forgot the fastest way jsfiddle.net/gx02o9nm - user208916
  • @Khipster, it's terrible. First, you replaced the array in the first call with a filtered one. Secondly, for an array of a couple of dozen elements, you do not measure the algorithm, but overhead. - Alexey Ten

Option using Set from ECMA2015 and Array.from

 var arr = [1,8,2,2,5,5,5,5,7]; document.write(JSON.stringify(arr),'<br/>'); var uniq = Array.from(new Set(arr)); document.write(JSON.stringify(uniq));

  • Um .. And the Set does the order of the elements save? - Qwertiy ♦
  • @Qwertiy, not sure, on a simple test - saved, but maybe this is not guaranteed - Grundy
  • I read. Saves: "Set objects represent collections of values ​​that you can crawl in the order of insertion of elements.". Suddenly. An interesting answer :) - Qwertiy ♦
  • @Qwertiy, added an example :) - Grundy

Given that repeats are in a row, you can change the source without an additional array: go through the elements, remembering the previous one, and deleting the repeats tails:

 var a = [8,2,2,5] ,i = 0 ,pValue // предыдущее значение ,pStart // первая позиция пред. зн. ,cValue // текущее значение ,length = 0 // длина фрагмента с повторами ; while( i++ < a.length) { cValue = a[i]; if( pValue === cValue) { length++; continue; } if(length) { a.splice(pStart,length); i -= length; } pValue = cValue; pStart = i; length = 0; } if(length) a.splice(pStart,length); document.body.innerText = JSON.stringify(a);

  • 2
    Somehow it looks ... Like the same approach ? But no, not the one. My elements are overwritten, which gives linear asymptotics, and then pieces are cut from the middle of the array, which gives a quadratic one. - Qwertiy ♦
  • Yes, complicated. You have an order of magnitude prettier! - Sergiks

Solution for your case (all the same elements are next):

 uniqArray = a.filter( (item, pos, arr) => !pos || item !== arr[pos - 1] );

Although I would just take a ready-made solution https://lodash.com/docs#sortedUniq