《剑指offer》面试题39. 数组中出现次数超过一半的数字

问题描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

输出: 2

限制：

1 <= 数组长度 <= 50000

代码

时间复杂度\(O(N)\),空间复杂度\(O(N)\)

class Solution {

public:

    int majorityElement(vector<int>& nums) {

        map<int,int> table;

        int n = nums.size(),ans;

        for(int& num:nums)

        {

            ++table[num];

            if(n % 2 == 0 && table[num] >= n/2 )

            {

                ans = num;

                break;

            }

            else if(n % 2 == 1 && table[num] >= n/2+1)

            {

                ans = num;

                break;

            }

        }

        return ans;

    }

};

结果

执行用时 :56 ms, 在所有 C++ 提交中击败了23.94%的用户

内存消耗 :19 MB, 在所有 C++ 提交中击败了100.00%的用户

代码

因为这个元素一定超过总个数的一半，因此我们排序后，中间的这个元素即为所求，时间复杂度\(O(N\log(N))\),空间复杂度\(O(1)\):

class Solution {

public:

    int majorityElement(vector<int>& nums) {

        int n = nums.size();

        if(n == 1)return nums[0];

        sort(nums.begin(),nums.end());

        return nums[n/2];

    }

};

结果

执行用时 :108 ms, 在所有 C++ 提交中击败了5.37%的用户

内存消耗 :18.9 MB, 在所有 C++ 提交中击败了100.00%的用户

代码

不同的元素相互抵消，剩下的元素一定是重复过半的。时间复杂度\(O(N)\)空间复杂度\(O(1)\)

class Solution {

public:

    int majorityElement(vector<int>& nums) {

        int ans,count = 0;

        for(int num:nums)

        {

            if(count == 0)

            {

                ans = num;

                ++count;

            }

            else{

                ans == num?++count:--count;

            }

        }

        return ans;

    }

};

结果

执行用时 :28 ms, 在所有 C++ 提交中击败了67.69%的用户

内存消耗 :18.7 MB, 在所有 C++ 提交中击败了100.00%的用户

巴特西

《剑指offer》面试题39. 数组中出现次数超过一半的数字

问题描述

代码

代码

代码

最新文章

热门文章