136. 只出现一次的数字

如果能用sort函数或者set容器就很简单，可惜不允许

异或解决

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;  
        for(int num : nums) {
            res ^= num;
        }      
        return res;                                                                                                                                                                                                  
    }
};

				

					
				
				

					
				
				

					
				
				

					
				
			

---

169. 多数元素

以空间换脑细胞 直接map+set

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> mp;
        unordered_set<int> st;
        for(int &num : nums) {
            st.insert(num);
            mp[num]++;
        }
        for(auto &num : st) {
            if(mp[num] > nums.size() / 2) return num;
        }
        return 0;
    }
};

				

					
				
				

					
				
				

					
				
				

					
				
			

---

75. 颜色分类

统计一下各颜色数量，再原地修改数组

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int cnt[3] = {0, 0, 0};
        for(int num : nums) cnt[num]++;
        for(int i = 0; i < cnt[0]; i++) nums[i] = 0;
        for(int i = cnt[0]; i < cnt[0] + cnt[1]; i++) nums[i] = 1;
        for(int i = cnt[0] + cnt[1]; i < cnt[0] + cnt[1] + cnt[2]; i++) nums[i] = 2;
    }
};

				

					
				
				

					
				
				

					
				
				

					
				
			

---

31. 下一个排列

想不到

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int pos1 = -1, pos2;
        for(int i = nums.size() - 1; i > 0; i--) {
            if(nums[i] > nums[i-1]) {
                pos1 = i;
                break;
            }
        }
 
        if(pos1 == -1) { //说明是最大排列
            reverse(nums.begin(), nums.end());
            return ;
        }
 
        for(int i = nums.size() - 1; i >= 0; i--) {
            if(nums[i] > nums[pos1 - 1]) {
                pos2 = i;
                break;
            }
        }
        cout << "pos1:" << pos1 << " " << "pos2:" << pos2 << endl;
        swap(nums[pos1-1], nums[pos2]);
        reverse(nums.begin() + pos1, nums.end());
    }
};

				

					
				
				

					
				
				

					
				
				

					
				
			

---

287. 寻找重复数

不能修改数组且只能用常量级额外空间

「二分查找」的思路是先猜一个数（搜索范围[left..right]里位于中间的数mid），然后统计原始数组中小于等于mid的元素的个数count：如果count严格大于mid，根据抽屉原理，重复元素就在区间[left..mid]里；否则，重复元素可以在区间[mid + 1..right]里找到

不是二分数字，而是二分下标，因为下标是有序的

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, mid, count;
        while(left < right) {
            mid = (left + right) / 2;
            count = 0;
            for(int &num : nums) {
                if(num <= mid) count++;
            }
            if(count > mid) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};