引言

??总结算法基本概念以及常见的算法思路。

基本概念

时间复杂度

在表达式中，只需要高阶项，去除低阶项和高阶项的系数，剩余部分f(n)，则时间复杂度为O(f(n))。

常数

常数操作：若一个操作和样本的数据量无关，每次都是固定时间内完成操作，则成为常数操作。

空间复杂度

排序算法

冒泡排序

算法

大的往后冒泡：

将序列中所有元素两两比较，将最大的数往后交换，冒泡到最后面。
将剩余序列中所有元素两两比较，将最大的数往后交换，冒泡到最后。
重复第2步，直到只剩下一个数。

代码

时间复杂度：O(n^2)

package com.test.selfcoding.algorithm.sort;

import com.test.selfcoding.utils.RandomArrayUtil;

import java.util.Arrays;

/**
 * @ClassNAME BubbleSort
 * @Description TODO
 * @Author Andya
 * @Version 1.0
 */
public class BubbleSort {

    public static void bubbleSort1(int[] arr) {
        /*
        1. 将序列中所有元素两两比较，将最大的数往后交换，冒泡到最后面n-1。
        2. 将剩余序列中所有元素两两比较，将最大的数往后交换，冒泡到上一次的最后前一个数n-1-i。
        3. 重复第2步，直到只剩下一个数。
         */
        int count = 0;
        // 第一层循环i: 0 ~ n-1
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
                count++;
            }
        }

        System.out.println("times: " + count);
    }

    public static void bubbleSort2(int[] arr) {
        /*
        1. 将序列中所有元素两两比较，将最大的数往后交换，冒泡到最后面n-1。
        2. 将剩余序列中所有元素两两比较，将最大的数往后交换，冒泡到上一次的最后前一个数n-1-i。
        3. 重复第2步，直到只剩下一个数。
         */
        int count = 0;
        // 第一层循环i: 0 ~ n-1
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;
            // 循环后若发现已经排序完毕，则无需进入交换
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = false;
                }
                count++;
            }

            //无任何交换，发现是顺序的，直接退出
            if (flag) {
                break;
            }

        }

        System.out.println("times: " + count);

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
//        int[] arr = {1, 2, 5, 2, 3, 6, 6, 8, 7, 4};
//        bubbleSort1(arr);
//        System.out.println(Arrays.toString(arr));

        int[] arr = {1, 2, 3, 4, 5, 6, 6, 7, 8};
        bubbleSort1(arr);
        System.out.println(Arrays.toString(arr));
        bubbleSort2(arr);
        System.out.println(Arrays.toString(arr));

        int[] arr1 = RandomArrayUtil.generateRandomArray(1000, 1000);
        int[] arr2 = RandomArrayUtil.copyArray(arr1);

        bubbleSort1(arr1);
        System.out.println(Arrays.toString(arr1));

        bubbleSort2(arr2);
        System.out.println(Arrays.toString(arr2));

    }

}

//结果
times: 36
[1, 2, 3, 4, 5, 6, 6, 7, 8]
times: 8
[1, 2, 3, 4, 5, 6, 6, 7, 8]
times: 8646
[-860, -843, -776, -760, -731, -696, -694, -694, -674, -659, -658, -655, -651, -641, -617, -604, -558, -556, -547, -544, -540, -524, -524, -519, -512, -496, -463, -439, -429, -407, -401, -362, -346, -335, -303, -291, -290, -277, -271, -267, -248, -239, -231, -228, -227, -221, -221, -219, -202, -181, -178, -153, -143, -142, -134, -113, -101, -75, -68, -50, -33, -33, -22, -16, 6, 16, 27, 36, 37, 41, 47, 57, 67, 75, 91, 96, 109, 119, 135, 146, 152, 159, 160, 175, 176, 192, 202, 211, 217, 218, 281, 281, 299, 313, 334, 354, 359, 359, 375, 377, 404, 409, 441, 445, 446, 459, 459, 472, 478, 488, 510, 514, 532, 553, 567, 580, 582, 583, 612, 635, 643, 661, 662, 680, 682, 693, 715, 742, 790, 792, 795, 814]
times: 8510
[-860, -843, -776, -760, -731, -696, -694, -694, -674, -659, -658, -655, -651, -641, -617, -604, -558, -556, -547, -544, -540, -524, -524, -519, -512, -496, -463, -439, -429, -407, -401, -362, -346, -335, -303, -291, -290, -277, -271, -267, -248, -239, -231, -228, -227, -221, -221, -219, -202, -181, -178, -153, -143, -142, -134, -113, -101, -75, -68, -50, -33, -33, -22, -16, 6, 16, 27, 36, 37, 41, 47, 57, 67, 75, 91, 96, 109, 119, 135, 146, 152, 159, 160, 175, 176, 192, 202, 211, 217, 218, 281, 281, 299, 313, 334, 354, 359, 359, 375, 377, 404, 409, 441, 445, 446, 459, 459, 472, 478, 488, 510, 514, 532, 553, 567, 580, 582, 583, 612, 635, 643, 661, 662, 680, 682, 693, 715, 742, 790, 792, 795, 814]

选择排序

算法

第一层循环先定义一个记录最小元素的下标，然后第二层循环一次后面的数组，找到最小的元素，最后将它放到前面排序好的序列。

代码

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

package com.test.selfcoding.algorithm;

import java.util.Arrays;

/**
 * @ClassNAME SelectionSort
 * @Description TODO
 * @Author Andya
 * @Date 2022/5/21 11:30
 * @Version 1.0
 */
public class SelectionSort {
    public static void selectionSort(int[] arr) {
        //空或者长度小于等于1，则直接返回，无需排序
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            // i ~ n-1上找到最小值下标
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }

            if (minIndex != i) {
                swap(arr, i, minIndex);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {1,5,3,7,8,4,2,1,2,6};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}

插入排序

算法

将第一个数和第二个数排序，构成一个有序序列；
将后面第三个数插入进去，构成一个新的有序序列；
依次对第四个数、第五个数……直到最后一个数，重复第二步。

代码

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

package com.test.selfcoding.algorithm;

import java.util.Arrays;

/**
 * @ClassNAME InsertionSort
 * @Description TODO
 * @Author Andya
 * @Version 1.0
 */
public class InsertionSort {

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 1; i < arr.length; i++) {
            // 让第 0~i 有序
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                //左边的大于右边的，则左右换位置，并且右边的一直往前比较，一直到下标为0或数比左边的大时就不用进入循环了。
                swap(arr, j, j + 1);
            }
        }

    }

    private static void swap(int[] arr, int j, int i) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 3, 4, 2, 7, 6, 9, 8};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

二分查找法

算法

常见应用

在一个有序数组中，找某个数是否存在。
在一个有序数组中，找大于等于某个数最左侧的位置。
局部最小值问题。（此处就不一定是有序，找中间数，若是局部最小值，则返回，若不是，左侧相邻的数和右侧相邻的数谁小，则二分到此区间必定有局部最小）

代码

时间复杂度：O(logN)

异或运算

算法

a ^ 0 == a
a ^ a == 0
满足交换律和结合律。

常见应用

不用额外的变量交换两个数。
一个数组中有1个数出现了奇数次，其他数都出现偶数次，查找这1个数。
一个数组中有2个数出现了奇数次，其他数都出现偶数次，查找这2个数。

算法应用：136. 只出现一次的数字

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

这种题目，我们就可以使用异或的如下两个特性进行求解：

一个数与本身异或，结果总是为 0
一个数与0异或，结果总是其自身

package com.test.selfcoding.algorithm;

/**
 * @ClassNAME SingleNumber
 * @Description TODO
 * @Author Andya
 * @Date 2022/5/21 17:01
 * @Version 1.0
 */
public class SingleNumber {

    public static int singleNumber(int[] nums) {
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //使用异或^运算
            //1. 一个数与本身异或，结果总是为0
            //2. 一个数与0异或，结果总是其自身
            ans = ans ^ nums[i];
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {4,1,2,1,2};
        System.out.println(singleNumber(nums));   //结果：4
    }

}

算法应用：389.找不同

389. 找不同

package com.test.selfcoding.algorithm;

/**
 * @ClassNAME FindTheDifference
 * @Description TODO
 * @Author Andya
 * @Date 2022/5/21 17:25
 * @Version 1.0
 *
 */
public class FindTheDifference {
    /**
     * 使用异或
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifferenceWithXOR(String s, String t) {
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            ans ^= s.charAt(i);
        }
        // 此时ans将s字符串中的所有字符拼接起来了
        for (int j = 0; j < t.length(); j++) {
            ans ^=  t.charAt(j);
        }

        return (char)ans;
    }

    /**
     * 使用位计数法
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifferenceWithCount(String s, String t) {
        // 26个字母大小的数组
        int[] letter = new int[26];

        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            //对应字符位置的数值+1
            letter[sChar - 'a']++;
        }

        for (int j = 0; j < t.length(); j++) {
            char tChar = t.charAt(j);
            //对应字符位置的数值-1
            letter[tChar - 'a']--;
            //找到负数的则为不同
            if (letter[tChar - 'a'] < 0) {
                return tChar;
            }
        }

        return ' ';
    }

    /**
     * 使用ASCII码计算
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifferenceWithASCII(String s, String t) {
        //将字符串s和t中每个字符的ASCII码的值求和，得到asciiS和asciiT
        int asciiS = 0, asciiT = 0;
        for (int i = 0; i < s.length(); i++) {
            asciiS += s.charAt(i);
        }

        for (int j = 0; j < t.length(); j++) {
            asciiT += t.charAt(j);
        }
        return (char) (asciiT - asciiS);
    }

    public static void main(String[] args) {
        String s = "abcdef";
        String t = "abcdfeg";
        System.out.println(findTheDifferenceWithXOR(s, t));
        System.out.println(findTheDifferenceWithCount(s, t));
        System.out.println(findTheDifferenceWithASCII(s, t)); //结果：g
    }

}

算法应用：寻找2个奇数次的数

package com.test.selfcoding.algorithm;

import java.util.Arrays;

/**
 * @ClassNAME Find2OddNumbers
 * @Description TODO
 * @Author Andya
 * @Date 2022/5/21 21:51
 * @Version 1.0
 */
public class Find2OddNumbers {

    //寻找一个数组中仅有的2个奇数次的数，假设a,b,c,c,d,d，则a和b即为要找的结果
    public static int[] find2OddNumbers(int[] arr) {
        //eor = a ^ b
        int eor = 0;
        for (int cur : arr) {
            eor ^= cur;
        }
        //若res1 = b 则，res2 = eor ^ res1
        //找到二进制最右边的1，取非，加1，再与自身
        // eor =   111010010
        // ~eor =  000101101
        //~eor+1 = 000101110
        //eor & (~eor+1) = 000000010
        int right = eor & (~eor + 1);
        int onlyOne = 0;
        for (int cur : arr) {
            //取一半，此二进制位为0或者为1，即为一半
            if ((cur & right) == 1) {
                onlyOne ^= cur;
            }
        }

        return new int[] {onlyOne, eor ^ onlyOne} ;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 3, 4, 2, 1, 3, 5, 4, 6, 7, 7};
        System.out.println(Arrays.toString(find2OddNumbers(arr))); //结果：[5,6]
    }

}

对数器

package com.test.selfcoding.algorithm;

import java.util.Arrays;

/**
 * @ClassNAME SelectionSort
 * @Description TODO
 * @Author Andya
 * @Date 2022/5/21 11:30
 * @Version 1.0
 */
public class SelectionSort {
    public static void selectionSort(int[] arr) {
        //空或者长度小于等于1，则直接返回，无需排序
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            // i ~ n-1上找到最小值下标
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }

            if (minIndex != i) {
                swap(arr, i, minIndex);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    //for test: 对数器 generate random array
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        // Math.random() -> [0,1) 所有的小数，等概率返回一个
        // Math.random() * N -> [0,N) 所有的小数，等概率返回一个
        // (int)(Math.random() * N -> [0,N-1]所有的整数，等概率返回一个

        //长度随机
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test: copy array
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        //新建一个数组
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test: is equals
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }

        if (arr1 == null && arr2 == null) {
            return true;
        }

        if (arr1.length != arr2.length) {
            return false;
        }

        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }

        return true;
    }

    // for test: sortArray
    public static void sortArray(int[] arr) {
        Arrays.sort(arr);
    }



    public static void main(String[] args) {
//        int[] arr = {1, 5, 3, 7, 8, 4, 2, 1, 2, 6};
//        selectionSort(arr);
//        System.out.println(Arrays.toString(arr));

        int testTime = 600000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            selectionSort(arr1);
            sortArray(arr2);
            if (!isEqual(arr1, arr2)) {
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                succeed = true;
                break;
            }
        }

        System.out.println("result: " + (succeed ? "succeeded" : "failed!"));

        int[] arr = generateRandomArray(maxSize, maxValue);
        System.out.println(Arrays.toString(arr));
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}