【C++】周赛#284 LeetCode#86 6031. 找出数组中的所有 K 近邻下标（双指针、模拟）Easy
第一次一题选手-2.13
第二次二题选手-2.19
第三次一题选手-2.27
第四次一题选手-3.5
第五次一题选手-3.13
You are given a 0-indexed integer array nums and two integers key and k. A k-distant index is an index i of nums for which there exists at least one index j such that |i - j| <= k and nums[j] == key.
Return a list of all k-distant indices sorted in increasing order.
Example 1:
Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1
Output: [1,2,3,4,5,6]
Explanation: Here, nums[2] == key and nums[5] == key.
Input: nums = [2,2,2,2,2], key = 2, k = 2
Output: [0,1,2,3,4]
Explanation: For all indices i in nums, there exists some index j such that |i - j| <= k and nums[j] == key, so every index is a k-distant index. Hence, we return [0,1,2,3,4].
Constraints:
-
1 <= nums.length <= 1000 -
1 <= nums[i] <= 1000 -
key is an integer from the array nums. -
1 <= k <= nums.length
以列表形式返回按 递增顺序 排序的所有 K 近邻下标。
示例 1：
输入：nums = [3,4,9,1,3,9,5], key = 9, k = 1
输出：[1,2,3,4,5,6]
解释：因此，nums[2] == key 且 nums[5] == key 。
输入：nums = [2,2,2,2,2], key = 2, k = 2
输出：[0,1,2,3,4]
解释：对 nums 的所有下标 i ，总存在某个下标 j 使得 |i - j| <= k 且 nums[j] == key ，所以每个下标都是一个 K 近邻下标。因此，返回 [0,1,2,3,4] 。
提示：
-
1 <= nums.length <= 1000 -
1 <= nums[i] <= 1000 -
key 是数组 nums 中的一个整数 -
1 <= k <= nums.length
题解
1、建立tmp数组，用左右双指针分别相向遍历nums数组，存储key的下标，直到left > right时跳出循环
2、对nums中的每个下标i遍历，j为tmp中的元素,如果|i - j| <= k，就将i加入到res中
易错点
for循环中的break语句
// 对nums中的每个下标i遍历,j为tmp中的元素,如果|i - j| <= k,就将i加入到res中
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < tmp.size(); ++j)
{
if (abs(i - tmp[j]) <= k)
{
res.push_back(i);
break; // 跳出最内部的for循环,i++
/*
没有break会出现WA,i不变j++
输入：[2,2,2,2,2]
2
(tmp = [0, 1, 2, 3, 4])
输出：[0,0,0,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4]
预期结果：
[0,1,2,3,4]
*/
}
}
}
AC代码
class Solution
{
public:
vector<int> findKDistantIndices(vector<int> &nums, int key, int k)
{
vector<int> res;
vector<int> tmp; // key的下标
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right)
{
if (nums[left] == key)
{
tmp.push_back(left);
left++;
}
else if (nums[right] == key)
{
tmp.push_back(right);
right--;
}
else
{
left++;
right--;
}
}
// 对nums中的每个下标i遍历,j为tmp中的元素,如果|i - j| <= k,就将i加入到res中
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < tmp.size(); ++j)
{
if (abs(i - tmp[j]) <= k)
{
res.push_back(i);
break; // 跳出最内部的for循环,i++
/*
没有break会出现WA,i不变j++
输入：[2,2,2,2,2]
2
(tmp = [0, 1, 2, 3, 4])
输出：[0,0,0,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4]
预期结果：
[0,1,2,3,4]
*/
}
}
}
return res;
}
};
复杂度
-
时间复杂度为 。其中C++ sort()时间复杂度为 -
空间复杂度为 。开辟tmp数组用于存储数组中key的下标