已知排序的array，或者不在乎去重之后的結(jié)果順序
Solution 1
可以做一次循環(huán)脆侮，判斷當(dāng)前的item是否等于前面那個item锌畸，如果不等于或不存在前面的item，就push到result中靖避。
時間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(n)
Array.prototype.uniq = function () {
if (!this.length || this.length == 0) return this;
this.sort();
var res = [this[0]];
for (var i = 1; i < this.length; i++) {
if (this[i] != this[i - 1]) res.push(this[i]);
}
return res;
}
Solution 2
采用兩個指針l和r潭枣，記錄不重復(fù)元素的位置，r從l的下一個開始遍歷數(shù)組幻捏，如果r位置的數(shù)字等于l位置的數(shù)字盆犁，說明該數(shù)字重復(fù)出現(xiàn)，不予處理篡九；如果r位置的數(shù)字不等于l位置的數(shù)字谐岁，說明該數(shù)字沒有重復(fù)，需要放到l的下一位置榛臼，并使l加1.
時間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)
Array.prototype.uniq = function () {
if (!this.length || this.length == 0) return this;
this.sort();
var left = 0, right;
for (right = left + 1; right < this.length; right++) {
if (this[left] != this[right]) {
this[++left] = this[right];
}
}
return this.slice(0, left + 1);
}
Solution 3
數(shù)組先排序伊佃，比較倆數(shù)組一頭一尾進(jìn)行去重。
Array.prototype.uniq = function () {
var res = [], end;
this.sort();
end = this[0], res.push(this[0]);
for (var i = 1; i < this.length; i++) {
if (this[i] != end) {
res.push(this[i]);
end = this[i];
}
}
return res;
}
如果數(shù)組順序雜亂
Solution 1
可以做一次循環(huán)沛善，用一個對象標(biāo)記該item是否存在航揉。如果不存在，就push到result中金刁。這里使用一個hashtable的結(jié)構(gòu)記錄已有的元素迷捧，這樣就可以避免內(nèi)層循環(huán)织咧。不過，假如數(shù)組非常龐大漠秋，這種做法的性能會差笙蒙。
Array.prototype.uniq = function () {
var hash = {}, result = [], item;
for (var i = 0; i < this.length; i++) {
item = this[i];
var key = Object.prototype.toString.call(item) + item;
if (!hash[key]) {
hash[key] = true;
result.push(item);
}
}
return result;
}
注意js中hash的鍵值是以字符存儲的，所以會自動將數(shù)組元素轉(zhuǎn)為字符型庆锦，因此作為hash索引時需要加上類型捅位，否則無法區(qū)分?jǐn)?shù)字1和字符1。
Solution 2
遍歷數(shù)組搂抒，建立新數(shù)組艇搀，利用indexOf判斷是否存在于新數(shù)組中，不存在則push到新數(shù)組求晶，最后返回新數(shù)組焰雕。時間復(fù)雜度為O(n^2)。
Array.prototype.uniq = function () {
var ret = [];
for (var i = 0; i < this.length; i++) {
if (ret.indexOf(this[i]) == -1) {
ret.push(arr[i]);
}
}
return ret;
}
Solution 3
遍歷數(shù)組芳杏，利用object對象保存數(shù)組值矩屁，判斷數(shù)組值是否已經(jīng)保存在object中，未保存則push到新數(shù)組并用object[arrayItem] = 1的方式記錄保存爵赵。
Array.prototype.uniq = function () {
var ret = [], tmp = [];
for (var i = 0; i < this.length; i++) {
if (!tmp[arr[i]]) {
tmp[arr[i]] = 1;
ret.push(arr[i]);
}
}
return ret;
}
Solution 4
數(shù)組下標(biāo)判斷法吝秕。遍歷數(shù)組。利用indexOf判斷元素的值是否與當(dāng)前元素索引相等空幻，如相等則加入烁峭。
Array.prototype.uniq = function () {
var res = [];
var me = this;
me.forEach(function (val, index) {
if (me.indexOf(val) == index)
res.push(val);
})
return res;
}
可以用filter過濾。
Array.prototype.uniq = function () {
var me = this;
var res = me.filter(function (x, index) {
return me.indexOf(x) == index;
});
return res;
}
Solution 5
將原數(shù)組中重復(fù)元素的最后一個元素放入結(jié)果數(shù)組中秕铛。
Array.prototype.uniq = function () {
var res = [];
for (var i = 0; i < this.length; i++) {
for (var j = i + 1; j < this.length; j++) {
if (this[i] == this[j]) j = ++i;
}
res.push(this[i]);
}
return res;
}
ES6
function unique(arr) {
return Array,from(new Set(arr));
}
