【刷题（17）】技巧

一 技巧基础

二 136. 只出现一次的数字

1 题目

2 解题思路

哈希表map

其实看到题目数组中某个元素出现的次数也可以直接用unordered_map容器统计每一个元素出现的次数，然后在遍历整个map容器查看是否有元素出现的次数等于1

3 code

class Solution {
public:
    int singleNumber(vector<int>& nums) {

        //第一次遍历，使用哈希来统计数组中元素出现次数
        unordered_map<int,int> map;
        for(int num:nums)
        {
            map[num]++;
        }
        
        //第二次遍历，查看是否有元素出现的次数等于1
        for(int num:nums)
        {
            if(map[num]==1) return num;
        }

        return 0;

    }
};

三 169. 多数元素

1 题目

2 解题思路

本题常见的三种解法：

• 哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N)O(N)O(N) 。
• 数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
• 摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N)O(N)O(N) 和 O(1)O(1)O(1) ，为本题的最佳解法。

哈希表+打擂台（边哈希，边打擂台，省去二次遍历哈希表在麻烦）

我们使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。

我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。

3 code

class Solution {
public:
    int majorityElement(vector<int>& nums) {

        unordered_map<int,int>map;//哈希
        int majority=0,cnt=0;//打擂台

        //哈希
        for(int num:nums)
        {
            map[num]++;

            //打擂台
            if(map[num]>cnt)
            {
                majority=num;
                cnt=map[num];
            }
        }
        return majority;

    }
};

四 75. 颜色分类

1 题目

2 解题思路

首先，所有数都≤2，那么索性把所有数组置为2，然后遇到所有≤1的，就再全部置为1，，覆盖了错误的2，这时候所有2的位置已经正确，最后所有≤0的全部置为0，也就覆盖了一些错误的1，这时候，0和1的位置都正确。最重要的就是需要两个指针指向下一个1或0的位置

3 code

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n0=0,n1=0;
        for(int i=0;i<nums.size();i++)
        {
            int num=nums[i];

            //先将所有在数置为2
            nums[i]=2;
            //如果数值小于等于1，将数置为1
            //(为0的时候，会将1的计数位前推一位)
            if(num<=1)
            {
            nums[n1]=1;
            n1++;
            }
            //如果数值小于等于0，将数置为0
            if(num<=0)
            {
                nums[n0]=0;
                n0++;
            }
        }
    }
};

五 31. 下一个排列

1 题目

2 解题思路

这道题是根据 维基百科 ,下图所示:

翻译过来：

先找出最大的索引 k 满足 nums[k] < nums[k+1]，如果不存在，就翻转整个数组；
再找出另一个最大索引 l 满足 nums[l] > nums[k]；
交换 nums[l] 和 nums[k]；
最后翻转 nums[k+1:]。
举个例子：

比如 nums = [1,2,7,4,3,1]，下一个排列是什么？

我们找到第一个最大索引是 nums[1] = 2

再找到第二个最大索引是 nums[4] = 3

交换，nums = [1,3,7,4,2,1];

翻转，nums = [1,3,1,2,4,7]

完毕!

所以,

时间复杂度：O(n)O(n)O(n)

空间复杂度：O(1)O(1)O(1)

3 code

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int cur=nums.size()-2;
        
        //前面大于后面在
        while(cur>=0&&nums[cur]>=nums[cur+1])
        {
            cur--;
        }

        //已经是最大数组了
        if(cur<0)
        {
            sort(nums.begin(),nums.end());
        }
        else
        {//表示找到国降序在一个位置
        int pos=nums.size()-1;
        while(nums[pos]<=nums[cur])
        {
            pos--;
        }

        swap(nums[cur],nums[pos]);
        reverse(nums.begin()+cur+1,nums.end());
        }

    }
};

六 31. 下一个排列

1 题目、

2 解题思路

题目要求查找重复的整数，很容易想到使用「哈希表」，但是题目中要求「只用常量级 O(1 的额外空间」，该方法不符合题意；
还可以考虑使用「力扣」第 41 题：缺失的第一个正数 的技巧，使用「原地哈希」，但是题目要求「你设计的解决方案必须不修改数组 nums」，该方法不符合题意；
但是题目中还说：「数字都在 1 到 n 之间（包括 1 和 n）」，查找一个有范围的整数，可以使用「二分查找」（这一点很重要，很多「二分查找」的问题就是要我们找一个整数）；
「快慢指针」的做法很有技巧，具体做法请见其它题解。

可以使用「二分查找」的原因

因为题目要找的是一个 整数，并且这个整数有明确的范围，所以可以使用「二分查找」。

重点理解：

这个问题使用「二分查找」是在数组 [1, 2,…, n] 中查找一个整数，而 并非在输入数组数组中查找一个整数。

使用「二分查找」查找一个整数，这是「二分查找」的典型应用，经常被称为「二分答案」。在 题解 中，「题型二」与「题型三」都是这样的问题。

央视《幸运 52》节目的「猜价格游戏」，就是「二分答案」。玩家猜一个数字，如果猜中，游戏结束，如果主持人说「猜高了」，应该猜一个更低的价格，如果主持人说「猜低了」，应该猜一个更高的价格。

继续 解题思路：每一次猜一个数，然后 遍历整个输入数组，进而缩小搜索区间，最后确定重复的是哪个数。

理解题意：

n + 1 个整数，放在长度为 n 的数组里，根据「抽屉原理」，至少会有 1 个整数是重复的；
抽屉原理：把 10 个苹果放进 9 个抽屉，至少有一个抽屉里至少放 2 个苹果。

方法：二分查找

「二分查找」的思路是先猜一个数（搜索范围 [left…right] 里位于中间的数 mid），然后统计原始数组中 小于等于 mid 的元素的个数 count：

如果 count 严格大于 mid。根据 抽屉原理，重复元素就在区间 [left…mid] 里；
否则，重复元素可以在区间 [mid + 1…right] 里找到，其实只要第 1 点是对的，这里肯定是对的，但要说明这一点，需要一些推导，我们放在最后说。

方法：快慢指针

数组形式的链表

题目设定的问题是 N+1 个元素都在 [1,n] 这个范围内。这样我们可以用那个类似于 ‘缺失的第一个正数’ 这种解法来做，但是题意限制了我们不能修改原数组，我们只能另寻他法。也就是本编题解讲的方法，将这个题目给的特殊的数组当作一个链表来看，数组的下标就是指向元素的指针，把数组的元素也看作指针。如 0 是指针，指向 nums[0]，而 nums[0] 也是指针，指向 nums[nums[0]].
这样我们就可以有这样的操作

C++
int point = 0;
while(true){
    point = nums[point]; // 等同于 next = next->next; 
}

链表中的环

假设有这样一个样例：[1,2,3,4,5,6,7,8,9,5]。如果我们按照上面的循环下去就会得到这样一个路径：1 2 3 4 5 [6 7 8 9] [6 7 8 9] [6 7 8 9] . . .这样就有了一个环，也就是 6 7 8 9。point 会一直在环中循环的前进。
这时我们设置两个一快(fast)一慢(slow)两个指针，一个每次走两步，一个每次走一步，这样让他们一直走下去，直到他们在重复的序列中相遇，

3 code

二分查找

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int len=nums.size();

        int left=1;
        int right=len-1;

        while(left<right)
        {
            int mid=(left+right)/2;

            //nums中小于等于mid的元素的个数
            int count=0;
            for(int num:nums)
            {
                if(num<=mid)
                {
                    count++;
                }
            }


            if(count>mid)
            {
                //下一轮搜索的区间[left..mid]
                right=mid;
            }
            else
            {
                //下一轮搜索的区间[mid+1..right]
                left=mid+1;
            }
        }
        //退出循环以后 left 与 right 重合，left （或者 right）就是我们要找的重复的整数；
        return left;

    }
};

快慢指针

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int slow = 0;
        int fast = 0;
        //快慢指针相遇
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        //快指针返回终点，继续出发
        fast = 0;
        while (nums[slow] != nums[fast]) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return nums[slow];
    }
};