数组中重复的数字

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数： 1
本文字数： 2.7k | 阅读时长 ≈ 3 分钟

　　在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。


代码：

方式一：（最愚蠢的做法，类似“不正统的冒泡排序2”）时间复杂度为T=O(n^2)
　　从numbers[i] (0<=i<=n-2)开始，分别与余下的numbers[i+1]~ numbers[n-1]进行比对，一旦找到重复的元素，就将其放到duplicate[0]中并返回true，否则返回false。
　　length为数组numbers的长度（似乎有点多余？）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if( numbers==null || numbers.length==0)
            return false; //非空判断
        length = numbers.length;
        for(int i=0; i<length-1; i++){
            for(int j=i+1; j<length; j++){
                if(numbers[i]==numbers[j]){
                    duplication[0]=numbers[i];
                    return true;
                }
            }
        }
        return false;
    }
}

方式二：
　　将数组元素转换成字符串装进StringBuffer中，然后从首末两端查找同一元素，若找到的两个下标不同，则说明该元素重复。时间复杂度为T=O(n),但是消耗内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
    StringBuffer sb = new StringBuffer(); 
        for(int i = 0; i < length; i++){
                sb.append(numbers[i] + "");
            }
        for(int j = 0; j < length; j++){
            if(sb.indexOf(numbers[j]+"") != sb.lastIndexOf(numbers[j]+"")){
                duplication[0] = numbers[j];
                return true;
            }
        }
        return false;
    }
}

　　
方式三：（建议这种）T=O(n)
　　题目里写了数组里数字的范围保证在0 ~ n-1 之间，所以可以利用现有数组设置标志，当一个数字被访问过后将标志位置为true。

1
2
3
4
5
6
7
8
9
10
11
12
//boolean只占一位，所以还是比较省的
public boolean duplicate(int numbers[], int length, int[] duplication) {
    boolean[] k = new boolean[length];
    for (int i = 0; i < k.length; i++) {
        if (k[numbers[i]] == true) {
            duplication[0] = numbers[i];
            return true;
        }
        k[numbers[i]] = true;
    }
    return false;
}

　　
方式四：（最机智的解法，但是我没咋明白）T=O(n)
　　不需要额外的数组，题目里写了数组里数字的范围保证在0 ~ n-1 之间，所以可以利用现有数组设置标志，当一个数字被访问过后，可以设置对应位上的数 + n，之后再遇到相同的数时，会发现对应位上的数已经大于等于n了，那么直接返回这个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean duplicate(int numbers[],int length,int [] duplication) {
        if( numbers==null || numbers.length==0)
            return false;

        for(int i=0; i<length; i++){
            int index = numbers[i];
            if (index>=length)  
                index-=length;

            if(numbers[index]>=length){
                duplication[0]=index;
                return true;
            }
            numbers[index] = numbers[index]+length;
        }
        return false;
}

---------------- The End ----------------
0%