Majority Number I

Problem

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

Note

遍历整个数组，用一个计数器count，找出超过整个数组长度二分之一的那个数res。规则是：当前数等于res，计数器加1；否则，计数器减1。若计数器为0，res更新为当前数num，计数器计1.

Solution

public class Solution {
    public int majorityNumber(ArrayList<Integer> nums) {
        int res = nums.get(0), count = 0;
        for (int num: nums) {
            if (count == 0) {
                res = num;
                count = 1;
            }
            else if (num == res) count++;
            else count--;
        }
        return res;
    }
}

Majority Number II

Problem

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.

Find it.

Notice

There is only one majority number in the array.

Example

Given [1, 2, 1, 2, 1, 3, 3], return 1.

Challenge

O(n) time and O(1) extra space.

Note

和上一道题异曲同工，由于多于数组长度三分之一的数可能有两个，那么我们设置两个计数器，找出这两个数；再用两个计数器重新计数，找出个数更多的那个数，就是所求。

Solution

public class Solution {
    public int majorityNumber(ArrayList<Integer> nums) {
        int size = nums.size();
        int a = 0, b = 0, ca = 0, cb = 0;
        for (int i = 0; i < size; i++) {
            if (nums.get(i) == a) ca++;
            else if (nums.get(i) == b) cb++;
            else if (ca == 0) {
                a = nums.get(i);
                ca++;
            }
            else if (cb == 0) {
                b = nums.get(i);
                cb++;
            }
            else {
                ca--;
                cb--;
            }
        }
        ca = cb = 0;
        for (int i = 0; i < size; i++) {
            if (nums.get(i) == a) ca++;
            else if (nums.get(i) == b) cb++;
        }
        return ca > cb ? a : b;
    }
}

Majority Number III

Problem

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

Find it.

Notice

There is only one majority number in the array.

Example

Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.

Challenge

O(n) time and O(k) extra space

Note

要求O(k)的space，即保证map的大小为k，但要通过所有的case，map的大小必须是k+1才满足，所以注意第8行的条件：
else if (map.size() < k+2) map.put(cur, 1);

其他的和上一道一样理解，建立一个HashMap，里面放入A中的不同的k+1个数，然后对这些数计数。当map的大小等于k+2时，统计map中所有的key，并将所有key对应的value减1，若value被减为0，就从map中移除这对键值。

这样，循环结束后，map中最多只剩下k个pair，找出其中value最大的key值，返回。

Solution

public class Solution {
    public int majorityNumber(ArrayList<Integer> A, int k) {
        if (A.size() < k) return -1;
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < A.size(); i++) {
            int cur = A.get(i);
            if (map.containsKey(cur)) map.put(cur, map.get(cur)+1);
            else if (map.size() < k+2) map.put(cur, 1);
            else {
                List<Integer> keys = new ArrayList();
                for (Integer key: map.keySet()) keys.add(key);
                for (Integer key: keys) {
                    map.put(key, map.get(key)-1);
                    if (map.get(key) == 0) map.remove(key);
                }
            }
        }
        int res = 0, val = 0;
        for (Integer key: map.keySet()) {
            if (map.get(key) > val) {
                val = map.get(key);
                res = key;
            }
        }
        return res;
    }
}