编写一个程序给定一个长度为 n 的整数数组 nums,数组中所有的数字都在 0∼n−1 的范围内。 数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。 请找出数组中任意一个重复的数字。
时间: 2023-02-13 17:57:13 浏览: 96
以下是 Python 代码:
```
def duplicateInArray(nums):
for i in range(len(nums)):
if nums[i] != i:
if nums[i] == nums[nums[i]]:
return nums[i]
else:
temp = nums[i]
nums[i] = nums[temp]
nums[temp] = temp
return -1
```
该算法的时间复杂度为 O(n)。
算法的思路如下:
1. 对于数组中的每个数字 nums[i],如果 nums[i] ≠ i,则将 nums[i] 放到它应该在的位置 nums[i]。
2. 如果 nums[i] = nums[nums[i]],说明 nums[i] 和 nums[nums[i]] 重复了。
3. 如果 nums[i] ≠ nums[nums[i]],则交换 nums[i] 和 nums[nums[i]]。
4. 重复步骤 1~3,直到找到重复的数字或者所有的数字都在正确的位置上。
这种算法的正确性在于,对于每个数字 nums[i],如果它不在它应该在的位置 nums[i],那么一定会被放到它应该在的位置。当所有的数字都在正确的位置上时,如果有重复的数字,则必定会有 nums[i] = nums[nums[i]]。
相关问题
编写一个C语言程序,给定一个整数数组 nums,将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
好的,下面是一个简单的 C 语言程序,可以实现你的要求:
```c
#include <stdio.h>
void moveZeroes(int* nums, int numsSize) {
int i, j = 0;
for (i = 0; i < numsSize; i++) {
if (nums[i] != 0) {
nums[j++] = nums[i];
}
}
for (i = j; i < numsSize; i++) {
nums[i] = 0;
}
}
int main() {
int nums[] = {0, 1, 0, 3, 12};
int numsSize = sizeof(nums) / sizeof(nums[0]);
moveZeroes(nums, numsSize);
for (int i = 0; i < numsSize; i++) {
printf("%d ", nums[i]);
}
return 0;
}
```
这个程序中,我们定义了一个函数 `moveZeroes`,它接受一个整数数组和数组的大小作为参数。该函数的作用是将数组中的所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。具体实现方式是,使用两个指针 i 和 j,i 从头开始遍历数组,j 记录下一个非零元素应该放置的位置,当遇到非零元素时,将该元素赋值给 nums[j],并将 j 加 1;最后,将 nums[j] 到 nums[numsSize-1] 的元素全部置为 0。
在主函数中,我们定义了一个示例数组 nums,调用了 `moveZeroes` 函数,然后输出结果。运行程序,输出的结果应该是:
```
1 3 12 0 0
```
希望这个程序能够帮到你!
给定整数数组nums和一个目标值target 在数组中找出和为目标值的两个整数 返回数组下标
题目描述:
给定一个整数数组 nums 和一个目标值 target,请在数组中找出和为目标值的两个整数,返回它们的数组下标。
示例:
输入:nums = [2, 7, 11, 15], target = 9
输出:[0, 1]
解释:nums[0] + nums[1] = 2 + 7 = 9,因此返回 [0, 1]。
思路:
暴力枚举法:对于每一个数,遍历整个数组,查找另一个数是否与它的和为目标值。
哈希表法:遍历数组,将每个数及其下标存储在哈希表中,同时查找哈希表中是否存在目标值减去当前数的差值。
代码实现:
暴力枚举法:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] == target) {
res.push_back(i);
res.push_back(j);
return res;
}
}
}
return res;
}
};
哈希表法:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
if (map.find(target - nums[i]) != map.end()) {
res.push_back(map[target - nums[i]]);
res.push_back(i);
return res;
}
map[nums[i]] = i;
}
return res;
}
};