多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
解题思路:首先看题目是求元素出现次数大于n/2的元素,第一种方案就是排序,然后找到位置为n/2的元素就一定是我们要找的元素,因为题目限定了一定存在多数元素,时间复杂度为O(nlogn),空间复杂度是O(1)。
代码如下:

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

第二种方案就是采用HaspMap保存元素出现的次数,然后判定count大于n/2就返回,时间复杂度为O(n),空间复杂度是O(n)。代码如下:

public int majorityElement(int[] nums) {
        int halfCount = nums.length / 2;
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
                if (1 > halfCount) {
                    return num;
                }
            } else {
                Integer count = counts.get(num);
                if (count + 1 > halfCount) {
                    return num;
                }
                counts.put(num, count + 1);
            }
        }
        return 0;
    }

以上两种方法的效率都不是最好的,排序算法花费了更多的时间,HashMap则占用了更多的空间。其实这道题可以类比现实世界中的擂台赛,每两个人pk,谁赢了就加一分,输了就减一分,最后谁还站在擂台上谁就是我们要找的数据,数组中的元素就是上擂台的元素,这种方法很巧妙,这也是算法的奇妙之处。时间复杂度为O(n),空间复杂度是O(1),具体代码如下:

public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += num == candidate ? 1 : -1;
        }
        return candidate;
    }

这道题目看似简单但是不同的方案的时间和空间复杂度是不一样的,这也就是算法在工作中的重要性,当数据量上去之后这个差异就是数量级上的差异,因此还是要多多思考。