面试中几种常见的数组问题

删除数组中重复元素

删除元素可以直接用Set集合，他会自动将重复的元素给去掉（下方注释的代码）

在一个给定的整型数组中，如何快速找到缺失的数字

假设一个长度为10的数组范围为1-9，快速定位到缺失的元素;定义一个map集合，以1-9为键，值为0，然后拿到上面数组的去遍历，相同则将值设为1，让后再去遍历map，值为0的键就是缺失的那个元素

    public static void main(String[] args) {
              //删除数组中重复的参数
/*      Object[] arr = {1,1,1,2,3,3,4,5,"夏","夏","冬","春",};
        Set set = new HashSet();
        //遍历数组并存入集合,如果元素已存在则不会重复存入
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }
        //返回Set集合的数组形式
        System.out.println(set.toArray()); 
*/
//在一个给定的整型数组中，如何快速找到缺失的数字
        List<Integer> ints = new ArrayList<>();
        ints.add(1);
        ints.add(2);
        ints.add(3);
        ints.add(4);
        ints.add(5);
        ints.add(6);
        ints.add(7);
        ints.add(8);
        ints.add(8);
        ints.add(9);
        HashMap<Object, Object> map = new HashMap<Object,Object>();
        map.put(1, 0);
        map.put(2, 0);
        map.put(3, 0);
        map.put(4, 0);
        map.put(5, 0);
        map.put(6, 0);
        map.put(7, 0);
        map.put(8, 0);
        map.put(9, 0);
        map.put(10, 0);
        for(Integer i : ints) {
            if(null!=map.get(i)) {
                map.put(i,1);
            }
        }
        for(Entry<Object, Object> entry : map.entrySet()) {
            if(entry.getValue().equals(0)) {
                System.out.println(entry.getKey());
            }
        }
    }

快速排序

static void quickSort(int[] arr,int left,int right)  //快速排序算法
    {
        int f,t;
        int rtemp,ltemp;
        ltemp = left;
        rtemp = right;
        f=arr[(left+right)/2];   //分界值
        while(ltemp<rtemp)
        {
            while(arr[ltemp]<f){
                ++ltemp;
            }
            while(arr[rtemp]>f){
                --rtemp;
            }
            if(ltemp<=rtemp){
                t=arr[ltemp];
                arr[ltemp]=arr[rtemp];
                arr[rtemp]=t;
                --rtemp;
                ++ltemp;
            }
        }
        if(ltemp==rtemp){
            ltemp++;
        }
        if(left<rtemp){
            quickSort(arr,left,ltemp-1);  //递归调用
        }
        if(ltemp<right){
            quickSort(arr,rtemp+1,right);  //递归调用
        }
    }

也可以直接使用

Arrays.sort(int[] arr)

注意：
Arrays.sort（） 无法直接对int【】数组进行降序排列，只能进行升序排列。
在使用排序时如果要求效率，最好使用int类型，而不是使用Integer类型，这样可以省去自动包装和拆包时所需要耗费的大量时间。

数组反转

直接使用数组实现反转

/**
     * 没有考虑效率的反转
     *
     * @param array
     * @return
     */
    private static int[] reverse1(int[] array) {
        int[] newArray = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            newArray[i] = array[array.length - 1 - i];
        }
        return newArray;
    }
 
    /**
     * 考虑时间复杂度和空间复杂度的反转
     *
     * @param array
     * @return
     */
    private static int[] reverse2(int[] array) {
        int temp;
        for (int i = 0; i < array.length / 2; i++) {
            temp = array[i];//将当前值赋给变量
            array[i] = array[array.length - 1 - i];//将后面的数据替换前面的数据
            array[array.length - 1 - i] = temp;//拿到前面的值赋后面
        }
        return array;
    }

通过工具类

 Collections.reverse(int[] array);

在指定数组中查找重复数字

public static   int findDuplicate(int[] nums) {
        if(nums == null||nums.length == 0) {
            return -1;
        }
        // 修改数组的方法 O(n)
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] - 1 != i) {
                int b = nums[i] - 1; // i所在的index
                int e = nums[b]; // i所在的index的值
                if (e == nums[i]) {
                    return e;
                } else { // 不一样 swap
                    int tmp = nums[b];
                    nums[b] = nums[i];
                    nums[i] = tmp;
                }
            }
        }
        return 0;
    }

求数组最大值

一般求数组最大值是通过遍历整个数据来获得最大值，这样遍历速度是O(n)

   public static void getMax(int[] arr) {
        int max = arr[0];
        for(int i=1;i<arr.length;i++) {
            if(arr[i]>max) {
                max = arr[i];
            }
        }
        System.out.println("该数组中最大的值为"+max);
    }

现在假设数组的元素从前到后先升序后降序，如果采用二分法的话可以相比较遍历全部而言他的速度是O（logn）。

public static void main(String[] args) {
        int[] arr = {3,4,5,6,7,8,9,10,11,12,13,10,9,8,7,6,4,3,2,1};
        int len = arr.length;
        // 当只有一个数时，直接返回
        if (len == 1) {
            System.out.println(arr[0]);
        }
        // 当数组只有下降部分时，直接返回
        if (arr[0] > arr[1]) {
            System.out.println(arr[0]);
        }
        // 当数组只有上升部分时，直接返回
        if (arr[len - 1] > arr[len - 2]) {
            System.out.println(arr[len - 1]);
        }

        // 接下来处理既有上升部分又有下降部分的数组（这样的数组至少有3个元素）
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (int) Math.floor((left + right) / 2);

            // 判断arr[mid]是否为最大值
            if (mid != 0 && arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                System.out.println(arr[mid]);
            }
            // 当arr[mid]不是最大值时，判断arr[mid]处于数组上升部分还是下降部分
            if (mid == 0 || arr[mid] > arr[mid - 1]) {
                // 处于上升部分
                left = mid + 1;
                System.out.println("left" + arr[left]);
            } else if (arr[mid] < arr[mid - 1]) {
                // 处于下降部分
                right = mid - 1;
                System.out.println("right" + arr[right]);

            }
        }
         System.out.println(arr[right]);
    }