多数元素 题解

题目详情 点击跳转->多数元素

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

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

示例 1：

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

示例 2：

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

提示：

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

解题思路与题解

思考过程：

在看到题干时，我们很容易想到的是，我们维护一个Map，然后Map的泛型为 <value,count>

然后遍历数组，并将值存入map中，最后判断哪一个value的count大于数组长度的一半，于是就有了如下解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int majorityElement(int[] nums) {
    Map<Integer, Integer> integerHashMap = new HashMap<>();
    for (int num : nums) {
        if (integerHashMap.containsKey(num)) {
            integerHashMap.put(num, integerHashMap.get(num) + 1);
        } else {
            integerHashMap.put(num, 1);
        }
    }
    int res = 0;
    for (Map.Entry<Integer, Integer> entry : integerHashMap.entrySet()) {
        Integer k = entry.getKey();
        Integer v = entry.getValue();
        if (v > nums.length / 2) {
            res = k;
        }
    }
    return res;
}

这是一种最简单的解法，时间复杂度为 O(2n) ，即我们会for循环两次

image-20231212202112106

但是，如果我们注意身体就会发现 题目中有这样一句话 你可以假设数组是非空的，并且给定的数组总是存在多数元素，此时我们需要注意，因为是必然有的所以，我们可以先排序，然后去取中间值，这样中间的值就必然是多数，所以我们的代码可以简化为

1
2
3
4
public static int majorityElementB(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length / 2];
}

image-20231212202146640

自己写排序算法，时间复杂度会更低一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int majorityElement(int[] nums) {
  int majorNum = nums.length / 2;
        int majorElement = 0;//由于假设必定存在多数元素，因此我们可以将其直接初始化，反正后续是会改变它的
        //尝试使用排序
        sort(nums,0,nums.length - 1);
        majorElement = nums[nums.length / 2];//当排序之后，由于多数元素大于该数组长度的1/2，因此中间位置的元素必然是多数元素，类似PigeonHole Principle
        return majorElement;
    }
    private void sort(int[] nums,int start, int end) {
        if (start >= end) {
            return;
        }
        //采用三路快速排序
        int pivot = nums[start];
        int lt = start;//指向最左端的pivot位置
        int gt = end;//指向最右端的pivot位置
        int i = start + 1;
        //i从左向右遍历，发现比pivot小的值就和lt交换，并lt++
        //发现比pivot大的就和gt交换，并gt--
        while (i <= gt){
            //我们还需要最后比较一次gt的位置的元素，因此要=时还继续遍历
            if (nums[i] < pivot) {
                int temp = nums[i];
                nums[i] = nums[lt];
                nums[lt] = temp;
                lt++;
            } else if (nums[i] > pivot) {
                int temp = nums[i];
                nums[i] = nums[gt];
                nums[gt] = temp;
                gt--;
                //但此处换过来的位置还需要继续比较，因此i不++
            } else {
                i++;
                //若等于pivot则直接往后走
            }
        }
        sort(nums,start,lt - 1);
        sort(nums,gt + 1,end);
    }
}

image-20231212202048315