力扣-统计数组中的元素
645. 错误的集合
题目描述
一个从 1 到 n 的整数集合，因为数据错误，导致一个数字重复出现，同时另一个数字丢失。要求找出这个重复的数字和丢失的数字。
思路分析
这是一个相对直接的问题。最直观的思路就是统计每个数字出现的次数。
使用辅助数组：我们可以创建一个大小为
n+1的数组st作为哈希表，用来记录数字1到n是否在输入数组nums中出现过。第一次遍历
nums：遍历nums数组，如果
st[x]已经是true，说明x是重复出现的数字，记录下来。否则，将
st[x]标记为true。
第二次遍历
1到n：遍历从1到n的整数，检查st数组。第一个st[i]为false的i就是那个丢失的数字。
这个方法的时间复杂度是 O(n)，空间复杂度是 O(n)。
代码实现
class Solution {
public:
// 定义一个足够大的数组来作为哈希表，防止越界
const int N = 1e4 + 10;
vector<int> findErrorNums(vector<int>& nums) {
// st 数组作为哈希表，记录数字是否出现过
vector<bool> st(N, false);
// res[0] 存放重复的数，res[1] 存放丢失的数
vector<int> res(2, 0);
// 第一次遍历：找出重复的数
for(int x : nums){
if(st[x]){ // 如果这个数已经出现过
res[0] = x; // 它就是重复的数
}
st[x] = true; // 标记该数已出现
}
// 第二次遍历：找出丢失的数
for(int i = 1; i <= nums.size(); i ++){
if(!st[i]){ // 如果数字 i 从未在 st 中被标记
res[1] = i; // 它就是丢失的数
break; // 找到后即可退出循环
}
}
return res;
}
};
697. 数组的度
题目描述
给定一个非空且只包含非负数的数组 nums，数组的“度”定义为数组里出现次数最多的那个元素的出现次数。要求找到一个和 nums 拥有相同“度”的、最短的连续子数组，并返回它的长度。
思路分析
这个问题的核心是找到出现频率最高的元素（可能不止一个），然后计算包含这些元素的、各自最短的连续子数组的长度，并从中取最小值。
统计信息：我们需要统计每个数字的三个关键信息：
出现次数。
第一次出现的位置（子数组的起点）。
最后一次出现的位置（子数组的终点）。
一次遍历：我们可以通过一次遍历来收集所有这些信息。
用一个数组
st记录每个数字的出现次数。用一个数组
s记录每个数字首次出现的位置。用一个数组
e记录每个数字最后一次出现的位置。在遍历过程中，同时记录下数组的“度”（即最大出现次数
maxx）。
二次遍历：遍历统计好频率的
st数组，找到所有频率等于maxx的数字。对于每个这样的数字i，其最短连续子数组的长度就是e[i] - s[i] + 1。我们在所有这些长度中取一个最小值即可。
代码实现
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
// st: 记录每个数字的出现次数 (frequency)
vector<int> st(50000 + 10, 0);
// s: 记录每个数字第一次出现的位置 (start)
vector<int> s(50000 + 10, -1);
// e: 记录每个数字最后一次出现的位置 (end)
vector<int> e(50000 + 10, -1);
int maxx = -1; // 记录数组的“度” (max frequency)
int ans = 60000; // 存储最终结果，初始化为一个较大值
// 第一次遍历：统计频率、起始和结束位置
for(int i = 0; i < nums.size(); i ++){
int x = nums[i];
if(st[x] == 0){ // 如果是第一次遇到这个数
s[x] = i; // 记录起始位置
}
e[x] = i; // 每次都更新最后出现的位置
st[x] += 1; // 频率加一
// 更新数组的“度”
if(st[x] >= maxx){
maxx = st[x];
}
}
// 第二次遍历：找到度相同的元素，计算最短子数组长度
for(int i = 0; i < 50010; i ++){
if(st[i] == maxx){ // 如果当前数字的频率等于数组的“度”
// 计算其子数组长度，并更新全局最小答案
ans = min(ans, e[i] - s[i] + 1);
}
}
return ans;
}
};
448. 找到所有数组中消失的数字
题目描述
给定一个范围在 [1, n] ( n 为数组大小) 的整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。要求不使用额外空间且时间复杂度为 O(n)。
思路分析
这道题是“原地哈希”思想的绝佳体现。核心思想是：将数组的下标和值进行映射。因为数字的范围是 [1, n]，正好可以和数组的下标 [0, n-1] 对应起来。
在这个解法中，我们采用了一种“标记-清空”的思路：
遍历数组：对于每个数字
nums[i]，我们把它看作一个“指令”，要去标记nums[i] - 1这个位置。原地标记：我们设计一个循环，只要当前位置
i的数x = nums[i]不是我们的标记值（比如-1），我们就一直追踪下去。我们跳到x - 1的位置，取出那里的数nx，然后将nums[x-1]的位置置为-1作为标记（表示x这个数字出现过）。然后，我们再以nx作为新的x继续这个过程，直到遇到一个已经被标记过的位置。寻找未被标记的位置：完成上述操作后，数组
nums中所有值为-1的位置j，都表示数字j+1曾经出现过。那么，那些值不为-1的位置j，就表示数字j+1从未出现过，也就是我们想找的消失的数字。
代码实现
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; i ++){
int x = nums[i];
// 只要当前值不是我们的标记值(-1)，就持续进行标记
while(x != -1){
int nextX = nums[x - 1]; // 暂存下一个要处理的值
nums[x - 1] = -1; // 将值 x 对应的位置标记为 -1，表示 x 出现过
x = nextX; // 继续处理下一个值
}
}
vector<int> res;
// 遍历标记后的数组
for(int i = 0; i < n; i ++){
if(nums[i] != -1){ // 如果位置 i 没有被标记
res.push_back(i + 1); // 说明数字 i + 1 消失了
}
}
return res;
}
};
442. 数组中重复的数据
题目描述
和上一题类似，给定一个范围在 [1, n] 的整型数组，其中一些元素出现了一次，一些出现了两次。找出所有出现两次的元素。要求不使用额外空间且时间复杂度为 O(n)。
思路分析
这同样是一道经典的原地哈希问题。相比上一题的标记清空，这里用了另一种标记方式：正负号标记法。
映射关系：我们依然利用值
v与下标v-1的对应关系。遍历与标记：遍历数组
nums。对于每个元素nums[i]：取其绝对值
val = abs(nums[i])，因为这个元素可能已经被前面的操作变成了负数。找到它对应的下标
idx = val - 1。检查
nums[idx]的符号：如果
nums[idx]是负数，说明val这个数字之前已经出现过一次了（是它把nums[idx]变负的），因此val是一个重复数字，将其加入结果集。如果
nums[idx]是正数，说明val是第一次遇到，我们将nums[idx]变为-nums[idx]，以此来标记val已经出现过一次。
完成遍历：遍历结束后，所有重复的数字都已被收集。
代码实现
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
int n = nums.size();
for (int i = 0; i < n; ++i) {
// 1. 获取当前值对应的目标下标。必须用 abs，因为前面的元素可能已将当前值变为负数。
int idx = abs(nums[i]) - 1;
// 2. 如果目标下标处的值是负数，说明该下标已被访问过。
// 这意味着 abs(nums[i]) 这个数字是第二次出现。
if (nums[idx] < 0) {
res.push_back(idx + 1); // 将其（原始值）加入结果
} else {
// 3. 如果是正数，说明是第一次访问。
// 将其变为负数，作为访问过的标记。
nums[idx] = -nums[idx];
}
}
return res;
}
};
41. 缺失的第一个正数
题目描述
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。要求算法的时间复杂度为 O(n)，并且只能使用常数级别的额外空间。
思路分析
这是原地哈希系列问题中难度较高的一道。目标是找到 1, 2, 3, ... 中第一个缺失的正数。
理想情况下，如果数组中没有缺失和重复，那么排序后 nums[i] 应该等于 i+1。我们的目标就是通过原地交换，尽可能地让数组达到这种“理想状态”。
原地交换归位：遍历数组，对于当前位置
i的元素nums[i]：我们希望数字
x能被放到下标为x-1的位置上。所以，只要
nums[i]是一个在[1, n]范围内的正数，并且它还没有在它应该在的位置上（即nums[i] != nums[nums[i] - 1]），我们就把它和它目标位置上的数进行交换。这个
while循环会一直进行，直到nums[i]不再是[1, n]范围内的数，或者它已经被放到了正确的位置上。nums[i] != nums[nums[i] - 1]这个判断是为了防止当目标位置已经是正确的值时（例如nums=[1,1]），发生无限交换。
寻找缺失数：经过上述操作后，数组中的数字尽可能地被“归位”了。我们再次遍历数组，找到第一个
nums[i] != i + 1的位置，那么i + 1就是我们寻找的第一个缺失的正数。特殊情况：如果遍历完发现所有数字都在正确的位置上（即
nums[i] == i + 1对所有i成立），这意味着从1到n都完整地出现了，那么第一个缺失的正数就是n + 1。
代码实现
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// 第一次遍历：通过原地交换，将数字 x 放到下标 x-1 的位置
for(int i = 0; i < n; i ++){
// 循环条件：
// 1. nums[i] 是正数且在 [1, n] 范围内
// 2. nums[i] 当前不在它应该在的位置上 (nums[i] != i + 1)
while(nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]){
swap(nums[i], nums[nums[i] - 1]);
}
}
// 第二次遍历：寻找第一个不满足 nums[i] == i + 1 的位置
for(int i = 0; i < n; i ++){
if(nums[i] != i + 1) {
return i + 1; // i+1 就是缺失的最小正整数
}
}
// 如果 [1, n] 都存在，那么缺失的就是 n + 1
return n + 1;
}
};
274. H 指数
题目描述
给定一个整数数组 citations，表示研究者的 n 篇论文的被引次数。H指数的定义为：一名科研人员的 h 指数是指他（她）的 (n 篇论文中) 至少有 h 篇论文分别被引用了至少 h 次。如果一个研究者有多种可能的 h 值，取最大值。
思路分析
H 指数的定义稍显绕口，但我们可以这样理解：将论文的引用次数从高到低排序，我们想找到一个点 h，使得引用次数最高的 h 篇论文，它们的引用次数都大于或等于 h。
排序：一个简单高效的方法是先对引用次数数组
citations进行排序。为了方便后续计算，我们采用升序排序。从后往前遍历：排序后，
citations[n-1]是最高的引用次数，citations[n-2]是次高的，以此类推。我们设
h为论文的数量。当
h=1时，我们看引用次数最高的 1 篇论文（即citations[n-1]），它的引用次数是否>=1。当
h=2时，我们看引用次数最高的 2 篇论文（即citations[n-2]和citations[n-1]），它们中最少的引用次数（即citations[n-2]）是否>=2。以此类推，当
h = n - i时，我们看引用次数最高的n - i篇论文，它们中最少的引用次数是citations[i]。我们只需要判断citations[i] >= n - i是否成立。
找到答案：我们从
i = 0到n-1遍历（相当于h从n到1）。第一个满足citations[i] >= n - i的n-i就是我们能找到的H指数。因为我们是从最大的h开始检查的，所以第一个满足条件的就是最大的 H 指数。特殊情况：如果循环结束都没有返回，说明所有论文的引用次数都为0，没有任何
h > 0满足条件，所以 H 指数是0。
代码实现
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
// 对引用次数进行升序排序
sort(citations.begin(), citations.end());
// 遍历数组，寻找满足条件的 h
// h 的值对应于 (n - i)，表示 h 篇文章
// citations[i] 是这 h 篇文章中被引用次数最少的那篇
for(int i = 0; i < n; i ++){
// 如果引用次数最少的那篇(citations[i])都大于等于文章数(n-i)
// 那么这 n-i 篇文章都满足条件，n-i 就是一个 h 指数
// 因为是从 h=n 往下找的，第一个满足的就是最大值
if(citations[i] >= n - i) {
return n - i;
}
}
// 如果循环结束都没有找到，说明没有任何 h>0 的 h 指数，返回 0
return 0;
}
};