[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;
    }