LeetCode 169. Majority Element

原创

大学里的混子

修改于 2018-10-30 16:58:34

4490

修改于 2018-10-30 16:58:34

文章被收录于专栏：LeetCode

169. Majority Element


Given an array of size n, find the majority element. The majority element is the element that
 appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority
 element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

题目大意：求数组中出现的次数超过n/2的数字。

解法一：

O(logn)的时间复杂度。

先对数组进行排序，然后取中间的数字就一定是出现次数大于n/2的数字。

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

好吧，如果写一篇文章就采用这么low逼的答案，估计又有人要喷了。

解法二：

O(n)的时间复杂度，O(n)的空间复杂度。

     public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> hashMap = new HashMap<>(); 
        for (int i = 0;i <nums.length;i++){
            if (hashMap.containsKey(nums[i])){
                hashMap.put(nums[i],hashMap.get(nums[i])+1);
            }else {
                hashMap.put(nums[i],1);
            }
            if (hashMap.get(nums[i])>nums.length/2){
                    return nums[i];
                }
        }
         return -1;
         
    }

解法三：

O(n)的时间复杂度，O(1)的空间复杂度。

思路：数组中有一个数字的出现次数超过一半，也就是说这个数字的出现次数比其他的所有的数字的出现次数之和还要多。因此我们可以考虑遍历数组的时候保存两个值，一个是数组中的数字，一个数次数。当我们遍历到下一个数字的时候，如果下一个数字与我们之前保存的数字是相同的，那么次数加1，不同则减1,。如果次数为0，那么我们需要保存下一个数字，并把次数设置为1,。由于我们要找到的数字比其他的所有的数字的出现次数还要高，那么我们要找的数字一定是最后一次把次数设置为1时候所对应的数字。

public int majorityElement(int[] nums) {
    int count=0, ret = 0;
    for (int num: nums) {

        if (count==0)
            ret = num;
        if (num!=ret)
            count--;
        else
            count++;
    }
    return ret;
}

解法四：

O(n)的时间复杂度。

这是一种采用快速排序中的partition()函数的方法。

后面会补上来

总结：无论从时间复杂度还是空间复杂度还是代码量上，解法三的算法的效率都是最好的。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

登录后参与评论

0 条评论

热度