题目一

    1. import java.util.Arrays;
    2. import java.util.HashMap;
    3. import java.util.Map;
    5. public class Array3 {
    6.     /**
    7.      * 面试题3：数组中重复的数字
    8.      * 题目一：找出数组中重复的数字。在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的。请找出数组中任意一个重复的数字
    9.      * 例如：如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复数字2或者3
    10.      */
    11.     public static void main(String[] args) {
    12.         //测试用例的选择
    13.         //正常数组{2,3,1,0,2,5,3}
    14.         //不正常数组{2,4,1,0}
    15.         //无效数组{},{9,9}
    16.         int[] test1 = {2, 3, 1, 0, 2, 5, 3};
    17.         int[] test2 = {2, 3, 1, 0};
    18.         int[] test3 = {};
    19.         int[] test4 = {9, 9};
    20.         System.out.println(function4(test1));
    21.         System.out.println(function4(test2));
    22.         System.out.println(function4(test3));
    23.         System.out.println(function4(test4));
    24.     }
    26.     //暴力解法
    27.     private static int function1(int[] array1) {
    28.         int length = array1.length;
    29.         if (length <= 1) {
    30.             return 0;
    31.         }
    32.         for (int j : array1) {
    33.             if (j > length) {
    34.                 return 0;
    35.             }
    36.         }
    37.         for (int i = 0; i < length; i++) {
    38.             for (int j = i + 1; j < length; j++) {
    39.                 if (array1[i] == array1[j]) {
    40.                     return array1[i];
    41.                 }
    42.             }
    43.         }
    44.         return 0;
    45.     }
    47.     //先排序，后暴力
    48.     private static int function2(int[] array2){
    49.         if(array2.length<=1||array2[array2.length-1]>array2.length){
    50.             return 0;
    51.         }
    52.         Arrays.sort(array2);
    53.         for(int i = 0; i< array2.length - 1;i++){
    54.             if (array2[i]==array2[i+1]){
    55.                 return array2[i];
    56.             }
    57.         }
    58.         return 0;
    59.     }
    61.     //哈希实现
    62.     private static int function3(int[] array3){
    63.         int length = array3.length;
    64.         if (length <= 1) {
    65.             return 0;
    66.         }
    67.         for (int j : array3) {
    68.             if (j > length) {
    69.                 return 0;
    70.             }
    71.         }
    72.         HashMap<Integer, Integer> check = new HashMap<Integer,Integer>();
    73.         for (int i : array3){
    74.             if(check.containsKey(i)){
    75.                 return i;
    76.             }else{
    77.                 check.put(i,1);
    78.             }
    79.         }
    80.         return 0;
    81.     }
    83.     //O(1)复杂度的实现
    84.     private static int function4(int[] array4){
    85.         int length = array4.length;
    86.         if (length <= 1) {
    87.             return 0;
    88.         }
    89.         for (int j : array4) {
    90.             if (j > length) {
    91.                 return 0;
    92.             }
    93.         }
    94.         for (int i = 0; i < array4.length; i++) {
    95.             if(array4[i]!=i){
    96.                 if(array4[i]==array4[array4[i]]){
    97.                     return array4[i];
    98.                 }else{
    99.                     //这里要注意先令temp = array4[array4[i]]，否则，再第三行赋值的时候会出问题
    100.                     int temp = array4[array4[i]];
    101.                     array4[array4[i]] = array4[i];
    102.                     array4[i] = temp;
    103.                     i--;
    104.                 }
    105.             }
    106.         }
    107.         return 0;
    108.     }
    111. }

    题目二

    /**
 * 面试题3：数组中重复的数字
 * 题目二：不修改数组找到重复的数字
 * 在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。找出数组中任意一个重复的数字，但不能修改输入的数组
 * 例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}那么对应的输出是重复的数字2或者3
 */
public class Array3_2 {
    public static void main(String[] args) {
        //测试用例的选择
        //正常数组{2,3,1,0,2,5,3}
        //不正常数组{2,4,1,0}
        //无效数组{},{9,9}
        int[] test1 = {2, 3, 1, 0, 2, 5, 3};
        int[] test2 = {2, 3, 1, 0};
        int[] test3 = {};
        int[] test4 = {9, 9};
        System.out.println(function2(test1));
        System.out.println(function2(test2));
        System.out.println(function2(test3));
        System.out.println(function2(test4));
    }
    //辅助数组
    private static int function1(int[] array1){
        if(array1.length<=1){
            return 0;
        }
        int[] arrayClone = new int[array1.length];
        for (int j : array1) {
            if(j>array1.length){
                return 0;
            }
            if (arrayClone[j] != 0) {
                return j;
            } else {
                arrayClone[j] = j;
            }
        }
        return 0;
    }

    //二分查找思想
    private static int function2(int[] arr){
        int low = 1;
        int high = arr.length - 1; // high即为题目的n
        int mid, count;
        while (low <= high) {
            mid = ((high - low) >> 2) + low;
            count = countRange(arr, low, mid);
            if (low == high) {
                if (count > 1)
                    return low;
                else
                    break;
            }
            //判断条件的选取要慎之又慎
            if (count > mid - low + 1) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 返回在[low,high]范围中数字的个数
     */
    public static int countRange(int[] arr, int low, int high) {
        if (arr == null)
            return 0;

        int count = 0;
        for (int a : arr) {
            if (a >= low && a <= high)
                count++;
        }
        return count;
    }

}