169. Majority Element

给定一个 array，输出超出半数的 item

一题多解，各种思路，面试热点问题。From 花花酱, 题解思路如下:

题目讲解视频截图

Solution 1: HashMap

Runtime: O(n), Space: O(n)

public int majorityElement(int[] nums) {
    int halfLen = nums.length / 2;
    Map<Integer, Integer> map = new HashMap<>();

    for (int num: nums) {
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
        if (map.get(num) > halfLen) {
            return num;
        }
    }

    return -1;
}

Solution 2: Sorting

Runtime: O(n * log n), Space: O(1)

public int majorityElement2(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length / 2];
}

Solution 3: Randomization

Runtime: O(n) on average, O(n^2) worst case
Space: O(1)
思路: 随机找item，数个数，平均两次能找到 majority Element

public int majorityElement(int[] nums) {
    int len = nums.length;
    int majority = -1;
    Random rand = new Random();
    boolean found = false;
    while (!found) {
        majority = nums[rand.nextInt(len)];
        int count = 0;
        for (int num: nums) {
            if (majority != num) {
                continue;
            }
            count++;
            if (count > len / 2) {
                found = true;
                break;
            }
        }
    }
    return majority;
}

(最优解) Solution 4: Boyer-Moore Vote

Runtime: O(n), Space:O(1)
思路：每次从 array 中取两个不同的数，然后删除这两个数；最后剩下的数就是 majority。

// 实现方式一：完全贴合上面的思路
public int majorityElement(int[] nums) {
    int majority = -1;
    int count = 0;
    for (int num: nums) {
        if (count == 0) {
            majority = num;
        }
        
        if (majority == num) {
            count++;
        } else {
            count--;
        }
    }

    return majority;
}

// 实现方式二：依然符合思路描述
public int majorityElement(int[] nums) {
    int majority = nums[0];
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == majority) {
            count++;
        } else {
            count--;
            if (count == 0) {
                i++;
                majority = nums[i];
                count = 1;
            }
        }
    }

    return majority;
}

// 实现方式三：通过了测试，但不确定是不是正确的。
public int majorityElement(int[] nums) {
    int majority = nums[0];
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == majority) {
            count++;
        } else {
            count--;
            // if (count < 0) {  // 也通过了测试
            if (count == 0) {
                majority = nums[i];
                count = 1;
            }
        }
    }

    return majority;
}

Solution 5: Bit Vote

思路：int type variable has 32 bits，每个 bit 都是 0 或 1. The majority element 在每个 bit 上的 value，都是所有 elements 在该 bit 上的 majority。

Java Shift 知识点:

>>>: unsigned shift
>> : signed shift, divide by 2

public int majorityElement(int[] nums) {
    int len = nums.length;
    int res = 0;
    for (int i = 0; i < 32; i++) {
        int bit = 1 << i;
        int oneCount = 0;
        for (int num: nums) {
            int currBit = (num & bit) >>> i;
            if (currBit == 1) {
                oneCount++;
            }
        }
        if (oneCount > len / 2) {
            res |= (1 << i);
        }
    }

    return res;
}

要注意处理Integer的负数情况，使用 unsigned shift 是解决方法之一。

// failed case: Integer.MIN_VALUE

for (int num: nums) {
  if ((num & bit) > 0) oneCount++;
}