看到这道题的第一眼想到的是先给它排序,然后双指针从左往右遍历,写了一个冒泡排序,但是我想到了应该会超时,因为冒泡时间复杂度是n的平方,输入大小时10000,肯定会超时,然后右又看了一下题目看到数字都是0-n-1,灵感一下子就来了,我先创建一个等大的自然数数组,数组里的数就是下标,然后遍历题目数组,每次每遍历到一个数就把自然数数组中下标为这个这个数的元素改成length(改成的数只要不是0-n-1都行,但必须统一),在改之前,先看看这个数是不是已经改了,如果已经改了说明前面已经出现这个数了,直接返回这个数即可。
class Solution {
public int findRepeatNumber(int[] nums) {
int length = nums.length;
int[] natureNum = new int[length];
int ans =0;
for(int i=0;i<length;i++){
natureNum[i] = i;
}
for(int i=0;i<length;i++){
if(natureNum[nums[i]] == length){
ans = nums[i];
return ans;
}else{
natureNum[nums[i]] = length;
}
}
return ans;
}
}
文章来源:https://www.toymoban.com/news/detail-504708.html
0毫秒,打败百分百用户,哈哈,我真是个天才。 文章来源地址https://www.toymoban.com/news/detail-504708.html
到了这里,关于剑指offer03.数组中重复的数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!