认识时间复杂度

常数时间的操作

一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
- 例如 int num = arr[i];中不管arr数组中有多少数据，每次赋值都是根据索引一次查询，都是固定时间内完成，是常数操作
- 而假如有链表list int num = list.get[i];中获取链表中的元素要逐个遍历，若获取第10万个数据需要10万次操作，所以不是常数操作

时间复杂度

拿选择排序来举例，选择排序是每一轮找到最小值，再与最前面的值交换。数组长度为N,总共下来会有多少次常数操作：
- 拿到数组中的元素是一次常数操作如arr[i] ，一轮排序中每个元素都会拿到，所以是N次
- 比较两个元素也是一次常数操作，一轮中每个元素都会比较一次，也是N次
- 找到最小的元素后，要与最前面的元素交换，一轮会交换 1次
- 总的下来：
  - 获取元素：N + N-1 + N-2 + ...
  - 进行比较：N + N-1 + N-2 + ...
  - 进行交换：1 + 1 + 1 + ... = N 次
  - 总共加起来可以写成 aN² + bN + c 次
  - 其中去掉低次项，去掉最高次项的系数也就是 N²
  - 时间复杂度为 O(N²)

简单排序算法

选择排序

前面已经说了选择排序的具体过程，直接看算法实现

public static void selectSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) { //  i~N-1 找最小值下标
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

冒泡排序

挨个比较，后者比前者大，则交换位置，最终一轮过后，最大的会被放到最后面，如同冒泡般冒出来
和选择排序一样，算法时间复杂度也为 O(N²)
代码实现：

/**
     *  小数往前冒
     * @param arr
     */
    public static void bubbleSort_0(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if(arr[j] < arr[j - 1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
    }
    /**
     *  大数往后冒
     * @param arr
     */
    public static void bubbleSort_1(int[] arr){
        for (int i = arr.length - 1; i > 0; i--) {
            for(int j = 0; j < i; j++){
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j+1] = temp;
                }
            }
        }
    }

异或运算

按位运算，相同为0，相异为1，也可以理解为无进位相加
异或性质：
- 1） 0 ^ N = N N ^ N = 0
- 2）满足交换律和结合律
- 推导出以下代码可以交换两数的值
- ```
// 令 a = 甲； b = 乙；
a = a ^ b;  //  a = 甲 ^ 乙 
b = a ^ b;  //  b = 甲 ^ 乙 ^ 乙 = 甲 ^（乙 ^ 乙）= 甲
a = a ^ b;  //  a = 甲 ^ 乙 ^ 甲 = （甲 ^ 甲）^ 乙 = 乙
// 最终 a = 乙，b = 甲；完成了两数的互换 
```
- 注意：该异或运算是对内存地址进行交换（数值相同也可以完成互换），若内存地址相同运算结果会为0；
  - 在数组的交换中慎用！（交换i和j位置时，i不能等于j）

例题：

一个数组中，只有一种数出现了奇数次，其他数都是偶数次，求这个奇数次的数。
- 利用异或的两个性质：交换律结合律以及 n ^ n = 0, 0^ n = n;
- 也就是说如果整个数组全部异或起来，出现偶数次的数最终都会变成0（通过结合律与交换律），最终留下的就只有奇数次的数

int eor = 0;
for(int i = 0; i < arr.length; i ++){
    eor ^= arr[i];
}
System.out.println(eor);

一个数组中，有两种数出现了奇数次，其他的数都是偶数次，求这两个数。
- 假设两个数是a和b，同上一题一样，全部异或一遍之后会得到 eor = a ^ b;
- 又因为 a 不等于 b，所以 eor 的值一定不等于 0 ，eor的二进制32位中，一定有某位是为1的（不可能全0）假设为第n位
- 说明第 n 位上，要么 a=0，b=1，要么a=1，b=0；
- 数组中第 n 位为 1 的数就有 a、b二者之一，以及偶数个第 n 位为 1 的其他数
- 再定义一个 eor2 = 0；仅遍历异或数组中数据的第n位为 1 数
- 就能够得到 a 或者 b 既 eor2 = a 或者 eor2 = b；
- eor ^ eor2 即为剩下的另一个数

int eor = 0;
for(int i = 0; i < arr.length; i ++){
    eor ^= arr[i];
}
// eor = a ^ b
// eor != 0  eor 必然有一个位置上是1 (二进制)
 
int rightOne = eor & (~eor + 1); // 位运算中提取出最右边的一：取反加一再相与

int eor2 = 0;
for(int i = 0; i < arr.length; i++){
    if(arr[i] & rightOne == 0){
        eor2 ^= arr[i];
    }
}
System.out.println(eor2 + " " + eor ^ eor2);