常见算法总结 - 数组篇

1.给定一个数值在1-100的整数数组，请找到其中缺少的数字。

找到丢失的数字 利用byte数组的1或0标记该数字是否被删除，例如byte数组下标为0的数值为1的话，代表数字1存在

public static void findmissnumber1(int[] ints) {
        // 声明一个byte数组
        byte[] isexist = new byte[100];
        for (int i = 0; i < ints.length; i++) {
            // 由于数值比下标大1， 0位置其实代表的是数字1
            isexist[ints[i] - 1] = 1;

        }
        for (int i = 0; i < isexist.length; i++) {
            if (isexist[i] == 0) {
                system.out.println("删除的数字是:" + ++i );
            }
        }
}

我们可以利用1-100的总和为5050，我们依次减掉数据内的所有值，得到的差值即为删除的值

public static void findmissnumber2(int[] ints) {
        int sum = 5050;
        for (int i = 0; i < ints.length; i++) {
            sum -= ints[i];
        }
        system.out.println("删除的数字：" + sum);
}

2.从数组中找出给定目标数字的两数组合。例如数组为{2, 3, 5, 7, 8, 9, 11, 14, 18}，给定数字给17，那么数组内的3+14=17。

先利用set存储对应的数字，然后再遍历数组，假设遍历到数字3的时候，检查set中是否存在（17-3）=14这个数字，如果存在的话，即存在这个组合。

public static void findpairnumber(int[] arrays, int target) {

        set<integer> existintegers = new hashset<>();
        for (int i = 0; i < arrays.length; i++) {
            existintegers.add(arrays[i]);
        }
        for (int i = 0; i < arrays.length; i++) {
            if (existintegers.contains(target - arrays[i])) {
                system.out.println("找到对应的数字组合：" + arrays[i] + "和" + (target - arrays[i]));
                // 去除掉已使用过的数字
                existintegers.remove(arrays[i]);
            }
        }
    }

3.将数组进行反转。

只需要将数组按中间位置为对称轴进行位置交换即可

public static void reversearray(int[] arrays) {

    for (int i = 0; i < arrays.length/2; i++) {

        int tmp = arrays[i];
        arrays[i] = arrays[arrays.length -1 - i];
        arrays[arrays.length -1 - i] = tmp;

    }

}

4.寻找数组中前k个最大的数。

我们新建一个长度为k的数组，遍历原数组，然后将大于k数组内的数字，放进k数组里，然后冒泡淘汰末尾的数字，最后剩下的就是前k个最大的数字。

public static int[] findkmaxints(int k, int[] ints) {

    int[] kints = new int[k];

    for (int i = 0; i < ints.length; i++) {
        // 如果大于kints 数组中的最后一个数字的话，直接插入
        if (ints[i] > kints[k - 1]) {
            kints[k - 1] = ints[i];
        }
        // 再进行冒泡
        bulb(kints);
    }

    return kints;
}


public static void bulb(int[] ints) {

    for (int i = ints.length-1; i >= 1; i--) {

        // 进行冒泡
        if (ints[i] > ints[i - 1]) {

            int tmp = ints[i];
            ints[i] = ints[i - 1];
            ints[i-1]=tmp;

        }

    }

}

5.求一个数组中连续子向量的最大和

遍历数组，从第一个大于0的数字开始累加，保存最大值，如果累加后的值小于等于0的话，就抛这一下标，从下一个下标开始累积，如果超过之前的最大值的话就进行替换。使用sum和max变量进行操作

public static integer findmaxsum(int[] ints) {
        if (ints.length == 0) {
            return null;
        }
        int currentsum = 0;
        int maxsum = 0;
        for (int i = 0; i < ints.length; i++) {
            currentsum += ints[i];
            if (currentsum < 0) {
                currentsum = 0;
            }
            if (currentsum > maxsum) {
                maxsum = currentsum;
            }
        }
        return maxsum;
}

6.一个数组中数字都两两重复，只有一个数字没有重复，如何找到那个数字？

我们可以将所有数字进行异或，两两重复的数字，都会被抵消掉，剩余最后的数字就是单个不重复的数字

public static integer findsinglenumber(int[] ints) {

        if (ints.length == 0) {
            return null;
        }
        int singlenumber = ints[0];
        for (int i = 1; i < ints.length; i++) {
            singlenumber ^= ints[i];
        }
        return singlenumber;
    }

7.将一个二维数组顺时针旋转90度.

先找出旋转90度，下标的变换规律。然后从外圈向内圈递归旋转变换。

public static void rollmatrix90(int[][] matrix, int circle) {

        // 当circle为0的时候为最外圈

        if (matrix.length - circle * 2 <= 0) {
            return;
        }

        int bound = matrix.length - circle - 1;

        for (int i = circle; i < matrix.length - 1 - circle; i++) {

            int a = matrix[circle][i];
            int b = matrix[i][bound];
            int c = matrix[bound][bound - i + circle];
            int d = matrix[bound - i + circle][circle];

            matrix[circle][i] = d;
            matrix[i][bound] = a;
            matrix[bound][bound - i + circle] = b;
            matrix[bound - i + circle][circle] = c;

        }

        rollmatrix90(matrix, circle + 1);

    }

原数组

1,2,3,4,5,
6,7,8,9,10,
11,12,13,14,15,
16,17,18,19,20,
21,22,23,24,25,

翻转后的数组

21,16,11,6,1,
22,17,12,7,2,
23,18,13,8,3,
24,19,14,9,4,
25,20,15,10,5,

8.找出数组的中位数。

使用快排的思想，但是只往中间位置进行排序，当最后的排序下标抵达数组中间位置的时，就是中位数。

public static int findmiddlenumber(int[] array, int begin, int end) {

        int beginrange = begin;
        int endrange = end;

        if (begin >= end) {
            return begin;
        }

        // 选择begin位置的数字作为分界点
        int splitnumber = array[begin];

        while (begin + 1 < end) {

            if (array[begin + 1] < splitnumber) {
                begin++;
                continue;
            }

            if (array[end] > splitnumber) {
                end--;
                continue;
            }

            int tmp = array[begin + 1];
            array[begin + 1] = array[end];
            array[end] = tmp;

        }

        int tmp = array[beginrange];
        array[beginrange] = array[begin];
        array[begin] = tmp;

        if (begin > array.length / 2) {

            return findmiddlenumber(array, beginrange, begin);

        } else {
            return findmiddlenumber(array, end, endrange);

        }

}

9.两个有序数组的合并排序

同时遍历两个数组，每次对比两个数组当前坐标的值哪个小，小的存入新的数组，数组下表往后移一位，大的那边坐标不变，继续下次大小对比。依次循环。

public static int[] mergesortarray(int[] arraya, int[] arrayb) {
        int[] sortarray = new int[arraya.length + arrayb.length];
        int aindex = 0;
        int bindex = 0;
        for (int i = 0; i < sortarray.length && aindex <= arraya.length && bindex <= arrayb.length; i++) {
            if (aindex == arraya.length) {
                sortarray[i] = arrayb[bindex++];
                continue;
            }
            if (bindex == arrayb.length) {
                sortarray[i] = arraya[aindex++];
                continue;
            }
            if (arraya[aindex] < arrayb[bindex]) {
                sortarray[i] = arraya[aindex];
                aindex++;
            } else {
                sortarray[i] = arrayb[bindex];
                bindex++;
            }
        }
        return sortarray;
    }

本文转自我的个人博客:《coderv的进阶笔记》
欢迎加入java后端架构技术讨论群：1398880
我的公众号：coderv的进阶笔记，记录技术心得