算法-多数元素-数组

多数元素

---

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

第一种简单解法：

对数组排序，数组一定存在多数元素的前提下，数组中间的元素一定是多数元素。
证明：排序之后，如果数组中间元素不是多数元素，则在中间元素左边或者右边最多有n/2个相同元素，与题目一定会出现多数元素的条件相悖。

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

第二种简单解法：

遍历数组，借助一个Map，以元素为key，value是元素出现次数
这个算法，关键是看空间复杂度是不是O(1)，考虑到最多有[n/2]个不同元素，所以最坏的空间复杂度是O(n)，不是很符合题意

 public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int count = counts.getOrDefault(nums[i], 0) + 1;
            //如果某个数字出现的个数已经超过数组的一半，自己返回
            if (count > length / 2)
                return nums[i];
            counts.put(nums[i], count);
        }
        return -1;
    }

第三种高端解法：

1，整数是32位二进制，从低位到高位判断是1还是0，所有位上的数确定了，这个多数元素就确定了
2，对于多数元素二进制某个确定的位，要么是1，要么是0。如果是1，遍历整个数组，所有数字在这个位上是1的次数大于[n/2]；如果是0，也是同样的道理。
3，反过来说，遍历数组，某个位上出现1的次数大于[n/2]，则多数元素的这个位上的值一定是1。
4，把多数元素所有为1的位找出来，多数元素也就确定了

public static int majorityElement(int[] nums) {

        int major = 0;
        int len = nums.length;
        for (int i =0,mask=1; i<32; i++,mask<<=1) {
            int binCount = 0;
            for(int num:nums) {
                if((num & mask) == mask) {
                    binCount++;
                }

                if (binCount > len/2) {
                    major |= mask;
                    break;
                }
            }
        }

        return major;

    }

第四种高端解法：摩尔投票

对数组的元素两两配对，如果两个数不同，则删除这两个数(逻辑上删除)，最后一定至少一个元素是无法完成配对的，这个数就是是那个多数元素

public static int majorityElement2(int[] nums) {
        int temp = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (count==0) {
                temp=num;
            }

            if (num == temp) {
                count++;
            } else if (num!=temp) {
                count--;
            }
        }

        return temp;

    }