JAVA算法-数组

数组是一种很常见的数据结构，知道索引，可以快速定位到具体元素，然而，数组中添加和删除元素会很慢，下面讲讲关于数组的一些算法题。

1. 一个二维数组，每一行从左到右递增，每一列从上到下递增， 输入一个二维数组和一个整数，判断数组中是否含有整数：

例如：二维数组如下，输入数字是12，则函数应该返回true。
1 4 8 9 10
2 5 9 11 12
5 7 10 12 14

解题思路：

我们知道这个二维数组横向是递增的，竖向也是递增的，我们拿输入的数字num = 12（假设输入的num是12），和数组的右上角元素a[0][n]比较，会出现三种情况，并对这三种情况做具体分析：

1) num > a[0][n] ，则num一定不在第一行，因此我们需要在第2、3...行来找;

2) num < a[0][n] ，则num一定不在第n列，因此我们需要在第n-1、n-2...列来找;

3) num = a[0][n] ，则返回true。

算法实现：

public static boolean findNumInArray(int[][] array, int num) {
        if (array == null) return false;
        int n = array[0].length - 1;
        int row = array.length;
        int m = 0;
        while (n >= 0 && m <= row - 1) {
            if (array[m][n] < num) {
                m++;
            } else if (array[m][n] == num) {
                return true;
            } else {
                n--;
            }
        }
        return false;
    }

时间复杂度：O(m+n)，空间复杂度O(1)。

2. 给定一个元素为1到N(N>=1)的正整型数组，找到1到N缺少的数字:

例如：假设N是5，数组元素是2，3，4，5，则需要找到缺少的数字1。

解题思路：

如果这个正整型的数组只缺少一个数字，且没有重复的数字，则我们可以这么做，分以下两步：

1）求1到N的和为total；

2）遍历数组，用total减去数组的每个元素，最后得到的值就是这个缺少的数字。

算法实现：

/**
     * 如果返回值是-1，则代表没有找到缺少的元素
     * @param array
     * @param N
     * @return
     */
    public static int findLeakNumInArray(int[] array, int N){
        int num = -1;
        if(array == null || N <= 0){
            return num;
        }
        if(array.length > 0){
            //求1到N的和
            int total = (1+ N) * N /2;
            for(int i = 0 ; i < array.length ; i++){
                //用和减去数组的元素，最后得到的就是缺少的元素
                total -= array[i];
            }
            num = total;
        }
        return num;
    }

时间复杂度：O(n)，空间复杂度O(1)。

延伸：假设1到N的正整型数组，缺少多个数字，且包含重复的数字，我们该怎么找到缺少的数字呢？

例如：假设N是5，数组元素是4，3，4，3，则需要找到缺少的数字1，2，5。

解题思路：

1）我们可以给new一个N+1的tmp数组，索引从1开始，到N结束；

2）遍历正整型数组array，并将元素array[i]作为tmp数组的索引，找到一个元素，tmp[array[i]]的值加1；

3）从1开始遍历tmp数组，找出值为0的对应的索引输出，即找到了缺失的数字。

算法实现：

public static void findLeakNumInArray1(int[] array, int N){
        if(array == null || N <= 0){
            return;
        }
        if(array.length > 0){
            int[] temp = new int[N +1];
            for(int i = 0 ; i < array.length ; i++){
                temp[array[i]] += 1;
            }

            System.out.print("leak num:");
            for(int i = 1 ; i < temp.length; i++){
                if(temp[i] == 0){
                    System.out.print( i + " ");
                }

            }
            System.out.print("\n");
        }
    }

时间复杂度：O(n)，空间复杂度O(n)。

3. 在给定的整数数组中，找出两个数相加的和等于给定的数字。

例如：给定的数组int[] a = {3,4,2,6,8}，target数字是5，则找到两个数相加和等于5的数字是3，2。

解题思路：

1）我们可以声明一个map，用来存储数组的元素和对应的索引；

2）遍历数组，用给定的数target减去a[i] ，判断（target-a[i]）在map是否存在：

不存在，则将a[i]和i添加到map中；

存在，则取出（target-a[i]）的索引和i，并返回对应的数字。

算法实现：

public static int[] findTwoNum(int[] array, int target){
        if(array == null || array.length <=0){
            return  null;
        }

        HashMap<Integer, Integer> recordMap = new HashMap<>();
        for(int i = 0 ; i < array.length; i++){
            if(recordMap.containsKey(target- array[i])){
                int indexOne = recordMap.get(target- array[i]);
                int indexTwo = i;
                return new int[]{array[indexOne], array[indexTwo]};
            }else{
                recordMap.put(array[i], i);
            }

        }
        return  null;

    }

时间复杂度：O(n)，空间复杂度O(n)。

4. 在给定的整数数组中，连续的几个数是重复的，请删除数组重复的数。

例如：给定数组int[] a = {3,3,3,4,2,2,6,5,5,8,9,10,10}，删除重复的数后，数组变成int[] a = {3,4,2,6,5,8,9,10}

解题思路：

我们使用两个指针，分别是慢指针cur，快指针pre，它们的初始值都是0，然后遍历数组，分以下两种情况讨论：

1）如果a[cur] != a[pre]，则cur++，同时赋值：a[cur] = a[pre]；

2）反之a[cur] = a[pre]，说明当前元素跟快指针遍历的元素是重复的，则继续往后遍历，找到不等重复步骤1，如果相等重复步骤2。

算法实现：

public static  void removeDupData(int[] data){
        if(data == null || data.length <=0 ){
            return;
        }
        int cur = 0;
        for(int pre = 0; pre < data.length; pre++){
            if(data[pre] != data[cur]){
                cur++;
                data[cur] = data[pre];
            }
        }

        int len = cur < data.length ? cur +1: data.length;

        System.out.print("remove duplicate data：");

        for(int i = 0; i < len; i ++){
            System.out.print(data[i] + " ");

        }
        System.out.print("\n");

    }

时间复杂度：O(n)。

4. 正整数反转：给定一个正整数123456，移动数组末位的N个元素，如N = 2，则输出56，1234；N = 4，则输出3456，12。

解题思路：

1）假设原始数组的长度为length，我们可以声明一个数组，可以先装载后面要移动的N个数字，再把原始数组前面（length - N）个数字向后移动N位，最后把存储到新数组的N个数字copy到原数数组的前N位。

注意事项：

移动N个元素跟移动 N%length 元素是一样的，如N = 7，则上面正整数移动7位变成 6，12345，跟 N % length = 7%6 = 1效果是一样的。

因此，我们新声明的数组的长度应该是 N%Length。

2）上面的解题思路会新开辟一个数组，我们想想有没有其它不用开辟内存空间的解法了。其实，这题跟字符串的反转是同一个思路：

例如给定一个字符串abcdef，反转字符串最后两位，则变成了ef,abcd。

我们解该题一般分为两部分，先反转整个字符串，再反转隔开后的两个字符串：

abcdef -> fedcba

fe dcba ->ef abcd

算法实现：

public static void rotateArray(int[] data, int times) {
        if (data == null || data.length <= 0 || times <=0) {
            return;
        }
        int rotateNum = times % data.length;

        //global inversion
        for (int start = 0, end = data.length -1; start <= end; start ++, end--){
            swap(data, start,end);

        }
        //local inversion
        for (int start = 0, end = rotateNum -1; start <= end; start ++, end--){
            swap(data, start,end);
        }
        //local inversion
        for (int start = rotateNum, end = data.length -1; start <= end; start ++, end--){
            swap(data, start,end);
        }


        for(Integer item: data){
            System.out.print(item);

        }
        System.out.print("\n");

    }


    public static void swap(int[] data, int start , int end){
        int tmp = data[start];
        data[start] = data[end];
        data[end] = tmp;

    }

测试代码：

public static void main(String[] args) {
      
        int[] data = {1,2,3,4,5,6};

        rotateArray(data, 4);

        System.exit(0);

    }

时间复杂度：O(n)。