LeetCode演算法題-Majority Element（Java實現）
這是悅樂書的第181 次更新，第183 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第40題（順位題號是169）。給定大小為n的陣列，找到陣列中出現次數超過n/2的元素。假設該陣列非空，並且該元素始終存在於陣列中。例如：
輸入：[3,2,3]
輸出：3
輸入：[2,2,1,1,1,2,2]
輸出：2
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
我們可以先將陣列排序，然後使用for迴圈遍歷前n-1個元素，使用count計算元素出現的次數。
如果第i個元素與第i+1個元素相等，並且i等於陣列長度減2，那麼count要加兩次，否則只用加1此，接著判斷count是否大於n/2，如果大於則返回第i個元素。
如果第i個元素與第i+1個元素不相等，這時需要判斷i是否大於0並且第i個元素與第i-1個元素是否相等，如果相等，count加1，接著判斷count是否大於n/2，如果大於則返回第i個元素，如果不相等，count歸為0，再重新開始迴圈。
因為題目已經表示陣列不會為空，所以不需要考慮特殊情況，但是有一點就要考慮，那就是如果沒有找到那個出現次數大於n/2的元素，需要返回陣列最後一個元素。
public int majorityElement(int[] nums) {
int size = nums.length / 2;
int result = nums[nums.length - 1];
Arrays.sort(nums);
int count = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
if (i == nums.length - 2) {
count++;
}
count++;
if (count > size) {
return nums[i];
}
} else {
if (i > 0 && nums[i] == nums[i - 1]) {
count++;
if (count > size) {
return nums[i];
}
} else {
count = 0;
}
}
}
return result;
}
此解法的時間複雜度是O(n log(n))+O(n)，空間複雜度是O(1)。
03 第二種解法
還是先利用Arrays的排序方法，將陣列排序。題目要找的是出現次數大於n/2的元素，那麼排過序後，假如存在該元素，那麼陣列的中間位元素，即nums[n/2]應該就是該元素。
但是，還需要一步判斷，如果陣列長度是偶數，比如是4，那麼中間位元素是nums[2]，即是陣列第三位元素，這時就需要判斷nums[1]和nums[0]是否相等了，如果相等那麼返回nums[0]或者nums[n/2 - 1]都行。
public int majorityElement2(int[] nums) {
int len = nums.length;
if(len == 1) return nums[0];
Arrays.sort(nums);
if (len%2 == 0 && nums[0] == nums[len/2 - 1]) {
return nums[0];
}
return nums[len/2];
}
此解法的時間複雜度是O(n log(n))，空間複雜度是O(1)。
04 第三種解法
取一臨時變數candidate，儲存出現次數大於n/2的元素。取一臨時變數count，儲存出現次數.
進入迴圈，判斷count是否等於0，等於0，就將當前元素賦值給candidate。接著判斷當前元素是否和candidate相等，相等的話count加1，否則減1，直到遍歷完所有元素。
此解法，關鍵在於，碰到當前重複元素就加1，沒碰到就減1，如果最後count不等於0，當前重複元素就是出現次數最多的元素，如果count變成0了，說明之前遇到的重複元素和不重複元素出現次數是相等的，相互抵消了，就需要重新去獲取當前重複元素了。
public int majorityElement3(int[] nums) {
int count = 0;
int candidate = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0) {
candidate = nums[i];
}
if (nums[i] == candidate) {
count++;
} else {
count--;
}
}
return candidate;
}
此解法的時間複雜度是O(n)，空間複雜度是O(1)。
05 第四種解法
使用HashMap，key儲存陣列元素，value儲存元素出現的次數，如果最後value值大於n/2，那麼該key就是出現次數最多的元素。
public int majorityElement4(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int freq = 0;
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
freq = map.get(nums[i]) + 1;
map.put(nums[i], freq);
} else {
freq = 1;
map.put(nums[i], 1);
}
if (freq > nums.length / 2)
return nums[i];
}
return nums[nums.length-1];
}
此解法的時間複雜度是O(n)，空間複雜度是O(n)。
06 測試與驗證
針對以上四種解法，使用隨機的陣列和編寫了簡易的測試程式碼來測試這幾種方法。如下：
public static void main(String[] args) {
Easy_169_MajorityElement instance = new Easy_169_MajorityElement();
int[] arg = { 3, 2, 3, 1, 2, 3, 2, 3};
long start = System.nanoTime();
int result = instance.majorityElement(arg);
long end = System.nanoTime();
System.out.println("majorityElement---輸入:" + Arrays.toString(arg) + " , 輸出:" + result + " , 用時:" + ((end - start) / 1000) + "微秒");
int[] arg2 = { 3, 2, 3, 1, 2, 3, 2, 3};
long start2 = System.nanoTime();
int result2 = instance.majorityElement2(arg2);
long end2 = System.nanoTime();
System.out.println("majorityElement2---輸入:" + Arrays.toString(arg2) + " , 輸出:" + result2 + " , 用時:" + ((end2 - start2) / 1000) + "微秒");
int[] arg3 = { 3, 2, 3, 1, 2, 3, 2, 3};
long start3 = System.nanoTime();
int result3 = instance.majorityElement3(arg3);
long end3 = System.nanoTime();
System.out.println("majorityElement3---輸入:" + Arrays.toString(arg3) + " , 輸出:" + result3 + " , 用時:" + ((end3 - start3) / 1000) + "微秒");
int[] arg4 = { 3, 2, 3, 1, 2, 3, 2, 3};
long start4 = System.nanoTime();
int result4 = instance.majorityElement4(arg4);
long end4 = System.nanoTime();
System.out.println("majorityElement4---輸入:" + Arrays.toString(arg4) + " , 輸出:" + result4 + " , 用時:" + ((end4 - start4) / 1000) + "微秒");
}
測試結果如下：
majorityElement---輸入:[1, 2, 2, 2, 3, 3, 3, 3] , 輸出:3 , 用時:211微秒 majorityElement2---輸入:[1, 2, 2, 2, 3, 3, 3, 3] , 輸出:3 , 用時:5微秒 majorityElement3---輸入:[3, 2, 3, 1, 2, 3, 2, 3] , 輸出:2 , 用時:4微秒 majorityElement4---輸入:[3, 2, 3, 1, 2, 3, 2, 3] , 輸出:3 , 用時:62微秒
07 小結
演算法專題目前已連續日更超過一個月，演算法題文章40 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！