当前位置：首页 > news >正文

【LeetCode 热题 100】只出现一次的数字 / 多数元素 / 颜色分类 / 寻找重复数

news 2025/6/13 18:54:28

⭐️个人主页：@小羊 ⭐️所属专栏：LeetCode 热题 100 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

只出现一次的数字

只出现一次的数字

在这里插入图片描述

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

多数元素

多数元素

在这里插入图片描述

常规哈希表。

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

投票法。

class Solution {
public:int majorityElement(vector<int>& nums) {int target = 0, cnt = 0;for (auto e : nums){if (e == target) cnt++;else if (--cnt < 0){target = e;cnt = 1;}}return target;}
};

颜色分类

颜色分类

在这里插入图片描述

class Solution {
public:void sortColors(vector<int>& nums) {int l = -1, r = nums.size(), i = 0;while (i < r){if (nums[i] == 0) swap(nums[++l], nums[i++]);else if (nums[i] == 1) i++;else swap(nums[--r], nums[i]);}}
};

下一个排列

下一个排列

在这里插入图片描述

class Solution {
public:void nextPermutation(vector<int>& nums) {int i = nums.size() - 2;while (i >= 0 && nums[i] >= nums[i + 1]) i--;if (i >= 0){int j = nums.size() - 1;while (j >= 0 && nums[i] >= nums[j]) j--;swap(nums[i], nums[j]);}reverse(nums.begin() + i + 1, nums.end());}
};

寻找重复数

寻找重复数

在这里插入图片描述

class Solution {
public:int findDuplicate(vector<int>& nums) {int fast = 0, slow = 0;do{slow = nums[slow];fast = nums[nums[fast]];} while (fast != slow);slow = 0;while (fast != slow){slow = nums[slow];fast = nums[fast];}return slow;}
};