剑指 Offer 03. 数组中重复的数字
利用题目的限制条件：所有数字都在 0～n-1 的范围内
通过交互让数字和下标一一对应，如果有多个数字对应同一个下标，那就找到了答案。文章来源：https://www.toymoban.com/news/detail-678108.html
class Solution {
public int findRepeatNumber(int[] nums) {
int n = nums.length;
int i = 0;
while(i < n){
if(nums[i] == i){ // 数字和下标对应了，往后寻找
i++;
continue;
}
if(nums[nums[i]] == nums[i]) return nums[i]; // 有两个数字对应同一个下标了，找到重复数字了
swap(nums, i, nums[i]); // 把nums[i]换到正确的位置
}
return 0;
}
void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
另一种写法文章来源地址https://www.toymoban.com/news/detail-678108.html
class Solution {
public int findRepeatNumber(int[] nums) {
int n = nums.length;
for(int i = 0; i < n; i++){
while(nums[i] != i) {
if(nums[i] == nums[nums[i]]) return nums[i];
swap(nums, i, nums[i]);
}
}
return 0;
}
void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
到了这里，关于剑指 Offer 03. 数组中重复的数字的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
