『壹』 深入分析數組去重
深入分析數組去重
數組去重是常見的面試考點，本文嘗試深入學習，總結並優化數組去重的實現方法。常見方法包括雙重循環法、查找元素第一次出現的位置、排序後去重以及使用散列表。
雙重循環法直接而直觀，創建新數組，逐個比較元素，時間復雜度為 O(n^2)。優化可改為forEach()方法，時間復雜度不變，代碼更簡潔。
查找元素第一次出現的位置方法從後往前遍歷數組，檢查元素位置是否首次出現，避免重復，空間復雜度為 O(1)。優化可標記刪除元素索引，減少元素搬移操作。
排序後去重方法使用JavaScript自帶排序演算法，檢查前後相鄰元素，若不相等則放入新數組。但該方法不適用於對象，因為對象不適合排序，且無法保證引用相同對象的變數相鄰。
使用散列表方法，通過對象實現，讀取數據時間復雜度為O(1)。對於JavaScript對象，需要改進鍵名以區分相同值的對象。時間復雜度可達到O(n)。
ES6的Set提供了新的數據結構，簡潔高效，支持多種類型的值作為鍵。不考慮NaN的去重，簡單檢查元素是否為NaN並進行去重。
lodash的uniq方法源碼實現類似於使用Set進行去重，當數組長度大於等於200時，會創建Set並轉換為數組去重，小於200時使用雙重循環並進行NaN去重。
總結：在開發中，通常處理的數組規模較小，無需過分關注性能問題。在工程實踐中，推薦使用ES6的Set轉數組方案實現去重，簡潔高效。具體場景選擇合適的去重方法，考慮「相等」的定義和場景需求，合理選擇合適的相等演算法。
『貳』 除去一個數組中的重復的數據有什麼好演算法
這個問題的意思是，如果假設一個數組中存在重復的數據項，那麼就中保留重復數據項中的一個。也就是說最終輸出的結果數組中不容許存在重復數據項，所以因為這里涉及到重復數據項的問題，所以立馬想到了集合(Set)這個數據結構，因為它是不容序存在重復數據項的數據結構，
思路1.也就是將數組中的所有元素插入到一個Set中，利用Set的自動剔除重復數據項的功能，將導致所有重復數據項沒有辦法插入成功，也就是add方法
返回false,然後調用toArray方法，返回這個集合所對應的數組。那麼這個數組就是一個沒有重復數據項的數組，利用這個方法，通過比較結果數組和
源數組之間的大小，查看源數組中到底是否存在重復數據項。
思路2.除了利用Set這個數據結構不容序存在重復數據項的功能之外，還有一種很容易想到的方法，也就是對整個數組進行排序，然後遍歷排序之後的數組，將重復數據項，清除掉。
思路1的實現：
public static int[] noDup(int[] array) {
Set<Integer> set = new
HashSet<Integer>();
for (int i :
array)
set.add(i);
Integer[]
integers = (Integer[]) set.toArray();
int[] result
= new int[integers.length];
for (int i =
0; i < integers.length; i++)
result[i] =
integers[i];
return
result;
}
思路2的實現:
使用快速排序等演算法對數組進行排序，這個排序過程不在介紹。假設下面這個演算法的輸入是一個幾經排好序的數組。
for (int i = 0; i < array.length - 1; i++) {
if (array[i]
== array[i + 1]) {
array[i] =
-1;
}
}
通過上面這段代碼就能夠實現把數組中所有的重復數據項只保留一個，其它的置為-1或者根據實際情況置成其它值。然後遍歷數據，刪除所有位-1的數據項，並且將數組中包含的記錄個數不斷減少即可。