题目描述
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内. 数组中某些数字是重复的, 但不知道有几个数字是重复的. 也不知道每个数字重复几次. 请找出数组中任意一个重复的数字. 例如, 如果输入长度为 7 的数组 {2,3,1,0,2,5,3}, 那么对应的输出是第一个重复的数字 2.
方法一: 双 for
时间复杂度: o(n^2) 空间复杂度 o(1)
时间复杂度太高了, 尽量避免啊
- public class Solution {
- // Parameters:
- // numbers: an array of integers
- // length: the length of array numbers
- // duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
- // Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
- // 这里要特别注意~ 返回任意重复的一个, 赋值 duplication[0]
- // Return value: true if the input is valid, and there are some duplications in the array number
- // otherwise false
- public boolean duplicate(int numbers[],int length,int [] duplication) {
- if(length<2) return false;
- for(int i=0;i<length;i++){
- for(int j=i+1;j<length;j++){
- if(numbers[i]==numbers[j]){
- duplication[0]=numbers[i];
- return true;
- }
- }
- }
- duplication[0]=-1;
- return false;
- }
- }
方法二: 加一个 boolean 量标志位
- public class Solution {
- // Parameters:
- // numbers: an array of integers
- // length: the length of array numbers
- // duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
- // Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
- // 这里要特别注意~ 返回任意重复的一个, 赋值 duplication[0]
- // Return value: true if the input is valid, and there are some duplications in the array number
- // otherwise false
- public boolean duplicate(int numbers[],int length,int [] duplication) {
- if(length<2) return false;
- boolean [] k=new boolean[length];
- for(int i=0;i<length;i++){
- if(k[numbers[i]]==true){
- duplication[0]=numbers[i];
- return true;
- }
- k[numbers[i]]=true;
- }
- return false;
- }
- }
来源: http://www.bubuko.com/infodetail-3031026.html