妥妥的去面试之数据结构与算法（一）

笔者由于在找工作，所以近期最主要的任务就是准备面试，不打无准备之仗。只有你准备充分了，那么你想要的机会才有机会入你怀中。

笔者会将准备面试的学习过程记录下来，方便自己复盘的同时也希望能给一道找工作的小伙伴们一些帮助。笔者准备的内容大纲如下

Android面试大纲.png

下面是数据结构与算法的正菜部分

一、找出数组中重复的数字

在一个长度为n的数组里的所有数字都在0~n-1的范围内。找出数组中任意一个重复的数字。

注意：如果题目改成找出数组中重复的数字的话，就需要和面试官沟通，我是找出所有重复的数字还是只需要找出一个就好了。

排序法

先把原数组进行一次排序，再对排序好的数组从头到尾进行遍历，很容易找到重复的数字，排序长度为n的数组需要O(nlogn)的时间。

哈希表法

可以借助哈希表解决该问题，从头到尾扫描该数组，判断该扫描到的数是否存在于该哈希表中，如果不存在则放于该哈希表中，如果存在则为重复元素。这个算法的时间复杂度是O(n),但却是以大小为O(n)的空间复杂度为代价。

交换法

如果没有重复元素的话，那么重排该数组后，数字i会出现在下标i的位置。如果有重复元素的话，下标i的位置可能不止一个数字，也可能没有数字。

从头到尾扫描数组，扫描到下标为i的数字（用m表示）看是否等于i，如果是则接着扫描下一个数字，如果不是，再拿它和下标为m的那个数字比较，如果相等，则找到一个重复数字，如果不相等，就和它交换。重复这样的操作，直到找到重复的数字。

代码实例：

如果不存在重复元素的话，返回-1（具体返回的值可以和面试官沟通）

public int getDuplicateNumber(int[] numbers){
        int len = numbers.length;
        if(numbers == null || len <= 0) return -1;
        for(int i=0;i<len;i++){
            if(numbers[i] < 0 || numbers[i] > len-1)
                return -1;
        }
        
        for(int i=0;i<len;i++){
            
            while(numbers[i] != i){
                if(numbers[i] == numbers[numbers[i]]){
                    return numbers[i];  //找到重复元素
                }
                else {
                    //交换numbers[i]和numbers[numbers[i]]的值
                    int temp = numbers[i];
                    numbers[i] = numbers[temp];
                    numbers[temp] = temp;
                }
            }
            
        }
        return -1;
    }

二、不能修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n的范围内。找出数组中任意一个重复的数字。不能改变原数组并且不可借助大小超过O(n)的辅助空间。

二分法

因为长度是n+1，所以该数组至少有一个重复的数字。可以根据长度进行一半一半的分割。比如长度为8的数组，把它分两半：1-4,5-7。先在数组中找在1-4范围内的数的个数，如果超过4个说明重复的数字在1-4中。这样就缩小了范围，之后继续二分，在数组中分别找1-2,3-4这两组数字的个数，直到找到一个重复的数字。

public int getDuplicateNumber2(int[] numbers){
        int len = numbers.length;
        if(numbers == null || len <= 0) return -1;
        int start = 1;
        int end = len-1;
        
        while(end >= start){
            int middle = ((end - start) >> 1)+start;
            int count = countRange(numbers,len,start,middle);
            if(end == start){
                if(count > 1) return start;  //找到重复元素
                else break;
            }
            if(count >(middle-start+1))
                end = middle;
            else
                start = middle+1;
        
        }
        return -1;
    }
    
private int countRange(int[] numbers, int len, int start, int end) {
        if(numbers == null)
            return 0;
        int count = 0;
        for(int i=0;i<len;i++){
            if(numbers[i]>=start && numbers[i]<=end)
                ++count;
        }
        return count;
    }

参考:剑指offer P39

面试系列的文章都放于 面试妥妥的 建议小伙伴们关注该专题