菜鸟笔记
提升您的技术认知

剑指offer

《剑指Offer》刷题目笔记

剑指Offer 数组

《剑指Offer》二维数组中的查找《剑指Offer》旋转数组的最小数字《剑指Offer》调整数组顺序使奇数位于偶数前面《剑指Offer》数组中出现次数超过一半的数字《剑指Offer》连续子数组的最大和《剑指Offer》把数组排成最小的数《剑指Offer》数组中的逆序对《剑指Offer》数字在排序数组中出现的次数《剑指Offer》数组中只出现一次的数字《剑指Offer》数组中重复的数字《剑指Offer》构建乘积数组

剑指Offer 字符串

《剑指Offer》替换空格《剑指Offer》字符串的排列《剑指Offer》第一个只出现一次的字符《剑指Offer》左旋转字符串《剑指Offer》翻转单词顺序序列《剑指Offer》把字符串转换成整数《剑指Offer》正则表达式匹配《剑指Offer》表示数值的字符串

剑指Offer 链表

《剑指Offer》从尾到头打印链表《剑指Offer》链表中倒数第k个结点《剑指Offer》反转链表《剑指Offer》合并两个排序的链表《剑指Offer》复杂链表的复制《剑指Offer》两个链表的第一个公共结点《剑指Offer》链表中环的入口结点《剑指Offer》删除链表中重复的结点

剑指Offer 树

《剑指Offer》重建二叉树《剑指Offer》树的子结构《剑指Offer》二叉树的镜像《剑指Offer》从上往下打印二叉树《剑指Offer》二叉树中和为某一值的路径《剑指Offer》二叉树的深度《剑指Offer》平衡二叉树《剑指Offer》二叉树的下一个结点《剑指Offer》对称的二叉树《剑指Offer》按之字顺序打印二叉树《剑指Offer》把二叉树打印成多行《剑指Offer》序列化二叉树

《剑指Offer》数组中出现次数超过一半的数字

阅读 : 1138

题目描述:

  数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

解题思路:

思路一:

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

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()){
            return 0;
        }
        // 遍历每个元素,并记录次数;若与前一个元素相同,则次数加1,否则次数减1
        int result = numbers[0];
        int times = 1;
        for(int i = 1; i < numbers.size(); ++i){
            if(times == 0){
                // 更新result的值为当前元素,并置次数为1
                result = numbers[i];
                times = 1;
            }
            else if(numbers[i] == result){
                times++;
            }
            else{
                times--;
            }
        }
        // 判断result是否符合条件,即出现次数大于数组长度的一半
        times = 0;
        for(int i = 0; i < numbers.size(); ++i)
        {
            if(numbers[i] == result){
                times++;
            }
        }
        return (times > (numbers.size() >> 1)) ? result : 0;
    }
};
思路二:

摩尔投票,这个方法我一开始也想到了,但是没有想到这竟然有理论解释,而且是大名鼎鼎的摩尔投票算法。

它的主要步骤是这样的:

  1. 初始化两个变量, cand 表示候选人,cnt 表示赞同它的票数。
  2. 如果 cnt = 0,那么 cand 就设置为当前的数字。
  3. 如果 cand 等于当前数字,那么票数 cnt 加一,否则票数减一。
  4. 最后 cand 就是得票超过一半的众数。
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> v) {
        int num = v[0], count_i = 1;
        for(int i = 1; i < v.size(); i++){
            if(v[i] == v[i-1]) count_i++;
            else {
                if(count_i <= 1) num = v[i];
                else count_i--;
            }
        }
        if (v.size() / 2 < count(v.begin(), v.end(), num)) return num;
        return 0;
    }
};
思路三:

哈希表,这个方法最简单,用哈希表记录每个数字出现的次数,最后看哪个数字次数超过一半就行了。

时间复杂度 O(n) ,空间复杂度 O(n) 。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> mp;
        for (auto x : nums) mp[x]++;
        for (auto [k, v] : mp) {
            if (v > n/2) return k;
        }
        return 0;
    }
};