[LeetCode]--169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Credits: Special thanks to @ts for adding this problem and creating all test cases.

给大家提供一个很nice的方法，因为题目有一点，多的数一定是占全部数的二分之一以上，所以遇到不同的就消除呗。剩下的绝对是那个大多数的数。

public int majorityElement(int[] nums) { int temp = 0, count = 0; for (int i = 0; i < nums.length; i++) { if (count == 0) { temp = nums[i]; count++; } else if (temp == nums[i]) count++; else count--; } return temp; }

最开始的两个小程序也贴上来吧，虽然都超时了，但是代码逻辑都是对的。

蛮力法

public int majorityElement(int[] nums) { if (nums.length == 0) return 0; int sum = 0; int max = 0, temp = 0; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length; j++) if (nums[i] == nums[j]) sum++; if (sum > max) { temp = i; max = sum; } sum = 0; } return nums[temp]; }

稍微改进一点点，但是还是超时了的普通算法。

public int majorityElement(int[] nums) { if (nums.length == 0) return 0; int[] flag = new int[nums.length]; Arrays.fill(flag, 0); for (int i = 0; i < nums.length - 1; i++) { if (flag[i] != 0) continue; for (int j = i + 1; j < nums.length; j++) { if (flag[j] != 0) continue; if (nums[i] != nums[j]) { flag[i] = 1; flag[j] = 1; break; } } } for (int i = 0; i < flag.length; i++) { if (flag[i] != 1) { return nums[i]; } } return 0; }