尋找清單中的第一個非重複元素

一、簡介

在本教程中，我們將探討查找清單中第一個非重複元素的問題。我們將首先了解問題陳述，然後實施一些方法來實現預期結果。

2. 問題陳述

給定一個元素列表，任務是找到列表中第一個不重複的元素。換句話說，我們需要識別清單中僅出現一次的第一個元素。如果沒有非重複元素，我們將傳回一個適當的指示，例如null 。

3.使用for循環

此方法使用嵌套的for迴圈來迭代列表並檢查重複元素。它很簡單，但效率較低。

3.1.執行

首先，我們迭代輸入列表中的每個元素。對於每個元素，我們透過再次迭代列表來檢查它是否僅在列表中出現一次。如果發現某個元素重複，我們將標誌isRepeating設為true 。如果發現某個元素不重複，則該方法傳回該元素。

以下是上述想法的實現：

Integer findFirstNonRepeating(List<Integer> list) {
 for (int i = 0; i < list.size(); i++) {
 int current = list.get(i);
 boolean isRepeating = false;
 for (int j = 0; j < list.size(); j++) {
 if (i != j && current == list.get(j)) {
 isRepeating = true;
 break;
 }
 }
 if (!isRepeating) {
 return current;
 }
 }
 return null;
 }

讓我們看一下範例列表：

[1, 2, 3, 2, 1, 4, 5, 4]

在第一次迭代期間，內部循環掃描整個列表以查找元素1的任何其他出現。它在索引4處找到元素1的另一個出現。由於元素1再次出現在清單中的其他位置，因此被視為重複。對元素2重複此過程。在第三次迭代中，它在列表中沒有找到元素3的任何其他出現。因此，它被識別為第一個非重複元素，並且該方法返回3 。

3.2.複雜性分析

令 n 為輸入清單的大小。外層循環迭代列表一次，導致 O(n) 次迭代。內部循環也針對每個外部循環迭代對列表進行一次迭代，從而導致每個外部循環迭代的迭代次數為 O(n)。因此，總體時間複雜度為O(n^2)。無論輸入清單的大小如何，此方法都使用恆定量的額外空間。因此，空間複雜度為O(1)。

此方法提供了尋找第一個非重複元素的簡單解決方案。然而，它的時間複雜度為 O(n^2)，這使得它對於大型清單效率低下。

4.使用indexOf()和lastIndexOf()

indexOf()方法檢索元素第一次出現的索引，而lastIndexOf()傳回最後一次出現的索引。透過比較清單中每個元素的這些索引，我們可以辨識出只出現一次的元素。

4.1.執行

在迭代中，我們檢查每個元素的第一次出現索引是否不等於其最後一次出現索引。如果它們不相等，則表示該元素在列表中出現多次。如果找到具有相同首次出現索引和最後一次出現索引的元素，則該方法會傳回該元素作為第一個非重複元素：

Integer findFirstNonRepeatedElement(List<Integer> list) {
 for (int i = 0; i < list.size(); i++) {
 if (list.indexOf(list.get(i)) == list.lastIndexOf(list.get(i))) {
 return list.get(i);
 }
 }
 return null;
 }

讓我們看一下提供的範例清單：

[1, 2, 3, 2, 1, 4, 5, 4]

在初始迭代期間， indexOf(1)和lastIndexOf(1)都傳回0和4 。他們不平等。這表示元素1是重複元素。對於後續元素2重複此過程。但是，當檢查元素3時， indexOf(3)和lastIndexOf(3)都傳回2 。這個等式意味著元素3是第一個非重複元素。因此，該方法傳回3作為結果。

4.2.複雜性分析

令 n 為輸入清單的大小。此方法循環存取列表一次。對於每個元素，它會呼叫indexOf()和lastIndexOf() ，這可能會迭代列表以查找索引。因此，總體時間複雜度為O(n^2)。這種方法使用恆定量的額外空間。因此，空間複雜度為O(1)。

雖然此方法提供了簡潔的解決方案，但由於其二次時間複雜度 (O(n^2))，因此效率較低。對於大型列表，特別是重複呼叫indexOf()和lastIndexOf() ，與其他方法相比，此方法可能會慢得多。

5.使用HashMap

另一種方式是，我們可以使用HashMap來統計每個元素的出現次數，然後找出第一個不重複的元素。這種方法比簡單的for迴圈方法更有效。

5.1.執行

在此方法中，我們迭代輸入列表以計算每個元素的出現次數並將它們儲存在HashMap中。計算出現次數後，我們再次迭代列表並檢查每個元素的計數是否等於1 。如果任何元素的計數等於1 ，則傳回該元素為第一個非重複元素。如果迭代整個清單後沒有找到非重複元素，則傳回-1 。

以下是上述想法的實現：

Integer findFirstNonRepeating(List<Integer> list) {
 Map<Integer, Integer> counts = new HashMap<>();

 for (int num : list) {
 counts.put(num, counts.getOrDefault(num, 0) + 1);
 }

 for (int num : list) {
 if (counts.get(num) == 1) {
 return num;
 }
 }

 return null;
 }

讓我們看一下提供的範例清單：

[1, 2, 3, 2, 1, 4, 5, 4]

第一次迭代後的counts將為：

{1=2, 2=2, 3=1, 4=2, 5=1}

迭代列表時， 1和2的計數大於1 ，因此它們不是不重複的。元素3的計數為1 ，因此它是第一個非重複元素。

5.2.複雜性分析

令 n 為輸入清單的大小。計算清單中每個元素的出現次數需要 O(n) 時間。迭代列表以查找第一個非重複元素也需要 O(n) 時間。因此，總體時間複雜度為 O(n) 。此方法使用與輸入清單中唯一元素的數量成比例的額外空間。在最壞的情況下，所有元素都是唯一的，空間複雜度為 O(n)。

此方法提供了一個有效的解決方案，可以在廣泛的輸入資料的清單中找到第一個非重複元素。它利用HashMap來追蹤元素的出現，與傳統的for循環方法相比，這顯著提高了效能。

6. 使用陣列作為頻率計數器

此方法使用陣列作為頻率計數器來計算每個元素的出現次數並找到第一個非重複元素。

6.1.執行

首先，我們初始化一個大小為maxElement + 1的陣列frequency ，其中maxElement是清單中的最大元素。我們迭代列表，並為每個元素num ，增加frequency[num] 。此步驟確保frequency[i]儲存元素i出現的次數。

接下來，我們再次遍歷列表。對於每個元素num ，我們檢查frequency[num]是否等於1 。如果frequency[num]為1 ，我們回傳num ，因為它是第一個非重複元素：

Integer findFirstNonRepeating(List<Integer> list) {
 int maxElement = Collections.max(list);
 int[] frequency = new int[maxElement + 1];

 for (int num : list) {
 frequency[num]++;
 }

 for (int num : list) {
 if (frequency[num] == 1) {
 return num;
 }
 }

 return null;
 }

讓我們看一下提供的範例清單：

[1, 2, 3, 2, 1, 4, 5, 4]

我們初始化頻率數組，將所有元素設為零：

[0, 0, 0, 0, 0, 0]

我們迭代列表：

Increment frequency[1] to 2.
 Increment frequency[2] to 2.
 Increment frequency[3] to 1.
 Increment frequency[4] to 2.
 Increment frequency[5] to 1.

接下來，我們再次迭代列表， frequency[1]和frequency[2]的值為2 ，所以它不是不重複的。對於frequency[3] ，該值等於1 ，因此該方法傳回3 。

6.2.複雜性分析

令 n 為輸入清單的大小。我們迭代列表兩次，但每次迭代的時間複雜度為 O(n)。這種方法比HashMap方法更節省內存，空間複雜度為 O(maxElement)。

當清單中的元素範圍較小時，此方法特別有效，因為它避免了散列的開銷並提供了更直接的實作。但是，如果輸入清單包含負數或零，則頻率陣列必須覆蓋可能元素的整個範圍，包括負數（如果適用）。

七、總結

下面是不同實作的比較表：

方法	時間複雜度	空間複雜度	效率	適合大型列表
使用for循環	O(n^2)	複雜度(1)	低的	不
使用indexOf()	O(n^2)	複雜度(1)	低的	不
使用HashMap	在）	在）	高的	是的
使用數組計數器	在）	O(最大元素)	高的	不

八、結論

在本文中，我們學習了幾種查找清單中第一個非重複元素的方法，每種方法都有其優點和注意事項。雖然每種方法都有其優點和注意事項，但 HashMap 方法因其識別第一個非重複元素的效率而脫穎而出。透過利用 HashMap，我們可以獲得最佳效能。

與往常一樣，範例的原始程式碼可 在 GitHub 上取得。