在 Java 中尋找數組的多數元素

一、簡介

在本教程中，我們將探索尋找數組中多數元素的不同方法。對於每種方法，我們將提供各自的程式碼實作以及時間和空間複雜性的分析。

2. 問題陳述

讓我們了解一下尋找數組中多數元素的問題。我們得到一個整數數組，我們的目標是確定其中是否存在多數元素。

多數元素比任何其他元素出現的頻率更高，超過了在數組中出現超過n/2次的閾值，其中n表示數組的長度。這意味著根據出現頻率來識別在陣列中占主導地位的元素。

在深入研究每種方法之前，我們將利用提供的範例資料作為輸入：

int[] nums = {2, 3, 2, 4, 2, 5, 2};

3.使用for循環

尋找多數元素的一種直接方法是使用for迴圈迭代數組。此方法涉及使用for迴圈迭代數組並維護每個元素的出現次數。然後，我們將檢查是否有任何元素滿足多數條件，這意味著它出現在數組的一半以上的槽中。

3.1.執行

在此實作中，我們使用for迴圈遍歷數組。對於數組中的每個元素，我們初始化一個計數變數來追蹤其出現次數。隨後，我們再次遍歷陣列來計算目前元素的出現次數。

當我們迭代數組時，如果遇到計數大於n/2的多數元素，我們可以立即返回該元素：

int majorityThreshold = nums.length / 2;
 Integer majorityElement = null;

 for (int i = 0; i < nums.length; i++) {
 int count = 0;
 for (int j = 0; j < nums.length; j++) {
 if (nums[i] == nums[j]) {
 count++;
 }
 }
 if (count > majorityThreshold) {
 majorityElement = nums[i];
 <span class="hljs-keyword">break</span>;
 }
 }

 assertEquals(2, majorityElement);

3.2.複雜性分析

for迴圈方法的時間複雜度為O(n^2) 。這種二次時間複雜度是由於實作中使用的巢狀循環而產生的，其中將數組中的每個元素與每個其他元素進行比較。另一方面，空間複雜度為O(1) 。

雖然此方法易於實現且空間開銷最小，但由於其時間複雜度為二次方，因此對於大型陣列來說並不是最有效的。

4. 使用排序方法

在這種方法中，我們利用排序演算法來有效地辨識數組中的多數元素。該策略涉及按升序對數組進行排序，這使我們能夠識別連續出現的元素。

假設多數元素出現的大小超過數組大小的一半，則排序後，它將佔據中間索引（如果數組長度為奇數）或緊鄰中間元素（如果數組長度為偶數）。因此，透過檢查排序數組的中間元素，我們可以確定其中一個是否符合多數元素的條件。

4.1.執行

首先，我們使用Arrays.sort()對陣列進行升序排序。這一步至關重要，因為它使我們能夠更輕鬆地識別連續出現的元素。接下來，我們迭代排序後的陣列並追蹤中間元素的出現次數。在循環內部，我們也檢查計數是否大於數組大小的一半。

如果是，則表示當前元素出現的次數超過一半，並且被識別為多數元素。然後代碼返回該元素。讓我們使用程式碼片段來示範這個概念：

Arrays.sort(nums);
 int majorityThreshold = nums.length / 2;
 int count = 0;
 Integer majorityElement = null;
 for (int i = 0; i < nums.length; i++) {
 if (nums[i] == nums[majorityThreshold]) {
 count++;
 }

 if (count > majorityThreshold) {
 majorityElement = nums[majorityThreshold];
 <span class="hljs-keyword">break</span>;
 }
 }

 assertEquals(2, majorityElement);

4.2.複雜性分析

由於排序，這種方法的時間複雜度通常為O(n log n) ，而空間複雜度為O(1) ，因為它使用恆定的額外空間。與for循環方法相比，此方法稍微更有效，但由於排序操作的時間，它可能不是非常大的數組的最佳解決方案。

5.使用HashMap

這種方法使用HashMap來儲存數組中每個元素的頻率。

5.1.執行

在這個方法中，我們迭代數組，增加HashMap中遇到的每個元素的計數。最後，我們迭代HashMap並檢查是否有任何元素的數量大於數組大小的一半。如果找到多數元素，我們將其返回；否則，我們傳回 -1 表示數組中不存在多數元素。

這是一個範例實作：

Map<Integer, Integer> frequencyMap = new HashMap<>();
 Integer majorityElement = null;

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

 int majorityThreshold = nums.length / 2;
 for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
 if (entry.getValue() > majorityThreshold) {
 majorityElement = entry.getKey();
 <span class="hljs-keyword">break</span>;
 }
 }

 assertEquals(2, majorityElement);

5.2.複雜性分析

總的來說，由於其線性時間複雜度，使用HashMap是一種更有效的方法，尤其是對於較大的資料集。由於遍歷一次數組和遍歷一次HashMap ，所以時間複雜度為O(n) 。

然而，這種方法需要額外的HashMap空間，這對於記憶體受限的環境來說可能是一個問題。在最壞的情況下，空間複雜度將為O(n)因為HashMap可能儲存陣列中的所有唯一元素。

6. 使用 Boyer-Moore 投票演算法

此演算法廣泛用於使用線性時間複雜度和固定記憶體量來尋找元素序列中的多數元素。

6.1.執行

在初始化步驟中，我們建立兩個變數：候選元素和計數。候選元素設定為數組中的第一個元素，計數設定為 1。

接下來，在迭代步驟中，我們循環遍歷數組中的剩餘元素。對於每個後續元素，如果當前元素與候選元素相同，我們就會增加計數。這意味著該元素也可能有助於成為多數。否則，我們減少計數。這抵消了先前對該候選人的投票。

如果計數達到 0，則候選元素將重設為當前元素，並且計數將設定回 1。這是因為如果先前的元素相互抵消，當前元素可能會成為多數元素的新競爭者。

迭代整個數組後，我們透過再次迭代數組並計算候選元素的出現次數來進行驗證。如果候選元素出現超過 n/2 次，我們將其作為多數元素返回。否則，我們返回-1。

讓我們繼續實施：

int majorityThreshold = nums.length / 2;
 int candidate = nums[0];
 int count = 1;
 int majorityElement = -1;

 for (int i = 1; i < nums.length; i++) {
 if (count == 0) {
 candidate = nums[i];
 count = 1;
 } else if (candidate == nums[i]) {
 count++;
 } else {
 count--;
 }
 }

 count = 0;
 for (int num : nums) {
 if (num == candidate) {
 count++;
 }
 }

 majorityElement = count > majorityThreshold ? candidate : -1;
 assertEquals(2, majorityElement);

以下是迭代步驟的細分：

Initial stage: [Candidate (2), Count (1)]
 Iteration 1: [Candidate (2), Count (0), Element (3)] // "3" != candidate, count--
 Iteration 2: [Candidate (2), Count (1), Element (2)] // "2" == candidate, count++
 Iteration 3: [Candidate (2), Count (0), Element (4)] // "4" != candidate, count--
 Iteration 4: [Candidate (2), Count (1), Element (2)] // "2" == candidate, count++
 Iteration 5: [Candidate (2), Count (0), Element (5)] // "5" != candidate, count--
 Iteration 6: [Candidate (2), Count (1), Element (2)] // "2" == candidate, count++

6.2.複雜性分析

此演算法的時間複雜度為O(n) ，空間複雜度為O(1) ，使其成為尋找數組中多數元素的有效解。

七、總結

表總結了每種方法的時間和空間複雜性及其優點。它提供了每種方法的權衡和優點的快速概述。

方法	時間複雜度	空間複雜度	優點缺點
For循環	O(n^2)	O(1)	– 易於實施
– 需要最少的額外空間
– 由於巢狀循環，大型數組效率低下
排序	O(n log n)	O(1)或O(n)	– 簡單的實現
– 如果使用就地排序，則不會產生額外的空間開銷
– 由於排序引入了額外的時間複雜度
HashMap	O(n)	O(n)	– 處理和空間使用的線性時間複雜度
– 有效處理大型陣列
– 需要額外的空間用於HashMap存儲
博耶-摩爾投票	O(n)	O(1)	– 最佳時間與空間複雜度
– 對大型陣列有效

八、結論

在本文中，我們探索了尋找數組中多數元素的各種方法。

for循環方法提供了簡單的實現，但由於其巢狀循環，對於大型數組來說效率低。 HashMap方法提供線性時間複雜度並有效處理大型數組，但它需要額外的HashMap儲存空間。

最後，Boyer-Moore 投票演算法提供了最佳的時間和空間複雜度，並且對於大型陣列非常有效。

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