常数操作：与数据量无关的操作
非常数操作：与数据量相关的操作
分析算法的好坏：先看时间复杂度的指标，在分析不同数据样本下的实际运行时间
比如同样的时间复杂度O(n).1000次的乘法运算和1000次的位运算，实际时间会有很大的差别
或运算 & 与运算 ^ 异或运算
空间复杂度： 只需要常数个额外空间的空间复杂度为O(1)
需要额外空间的个数与数据量相关的算法的空间复杂度为O(n)
与运算（&）：两个数同时为1，结果才为1，否则为0
- 可以用于清0，把一个数与0做与运算
- 取特定位置的数，把要取位置的数设置为1，其他位置设置为0，与代取数进行与运算即可
异或运算(^) : 相同得 1 ，不相同得0，还可以理解为不进位相加
或运算（|）：两位中只要有1位是1，结果就是1
- 可以用于把某些位置置1，X = 1010 0000 ,设 Y= 0000 1111 X | Y = 1010 1111 把后四位置为1了
取反(~)：0->1，1->0
异或运算的性质：1100 0011 0100 -> & 0100
- 0 ^ N = N N ^ N = 0
- 满足交换律和结合律 a ^ b = b ^ a a ^ b ^ c = a ^ c ^ b(同一批数异或的结果一样)
这种交换算法必须要保证a b的内存地址是不同的， 如果 a b 的内存地址相同，那么这个内存地址就会被异或为0
案例：
1 . (在时间复杂度 O(n), 空间复杂度O(1)的情况下)，有一个数组，长度为n,其中有一种数只出现奇数次，其他数都出现偶数次，找出这个出现奇数次的数
2. (在时间复杂度 O(n), 空间复杂度O(1)的情况下)，有一个数组，长度为n,其中有两种数只出现奇数次，其他数都出现偶数次，找出这两个出现奇数次的数
答案：
- 数组中的所有数异或运算
- 令 eor = 数组中所有数异或，找出eor的二进制表示中等于1的位置，让eor与数组中，这个位置为 1 或者 0 的数来异或，得到a或者b,把得到的结果与eor运算，得到另外一个数
用 与运算 提取 最右边的 1
插入排序
从左到右，保证逐次有序（保证每次排序结束后，右边的数都大于等于其左边的数）
这种算法的时间复杂度与数据的情况有关，估计这种算法的时间复杂度用最差情况来估计
O(n^2)
二分查询的的时间复杂度是
局部最小问题
1 . 先判断 0 位置 和 n -1 位置, 如果没找到，可以证明在0 - n -1 一定存在局部最小
2. 之后判断中点位置，如果中点位置不是局部最小，那么 0 - 中点 和 中点 - n - 1 一定存在局部最小
这样二分下去一定可以找到至少一个局部最小
（这种二分策略是建立在相邻的数一定不想等的情况下的）
（当发现数据状况或者问题是有关于数据左右的时候，就可以使用二分）
不追求时间复杂度策略，但是很好想的方法是方法B
对数器是帮助我们测试方法的正确性的
递归求数组最大值
对于上述的问题的时间复杂度可以用master公式求解
T(N)是指 母问题的数据量是N个 ，子问题的规模是b/N个 ， a是子问题被调用了多少次，O(N^d)是指除了
递归以外其他操作的时间复杂度
则 求最大值的时间复杂度 为 T(N) = 2 * T(N / 2) + O (1)
只要是等规模的递归，都可以用master公式求解时间复杂度
归并排序没有浪费比较行为，每一次的比较行为最终都会保留下来成为一个新的有序的数组
求小和问题
求一个数左边有多少个数比这个数小 可以转换为 求一个数右边有多少个数比这个数大
注意：这种求小和的方法与传统的MergeSort有点差别，传统的MergeSort在Merge的时候遇到2个数相等的情况通常会先拷贝左边的数，但是求小和的时候必须先拷贝右边的数，如果先拷贝左边的数，就会导致有部分的小和丢失
相等的情况下，先拷贝左边的数字，会导致被拷贝的左边的数字不能与右边比它大的数字组合，无法产生小和，导致小和丢失
小和产生的根本是左边的数字，如果在相等的情况下直接拷贝左边的数字，那么后续若是右边的数字中依然存在比被拷贝的左边数字还要大的数字，就不能与被拷贝的左边的数字产生小和了
总结一下：哪边需要运用下标运算，哪边在相等的情况下就先拷贝。
逆序对问题
在一个数组中，左边的数如果比右边的数大，就可以组成一个逆序对，求一个数组中有多少逆序对
逆序对的定义是求左边的数比右边的数大，可以转换为求右边的数比左边的数小来求
public static int reverseOrder(int[] arr){
if(arr == null arr.length <= 1){
return 0;
}
return reverseOrderProcess(arr, 0, arr.length-1);
}
public static int reverseOrderProcess(int[] arr, int L, int R){
if(L == R){
return 0;
}
int M = L + ((R - L) >> 1);
return reverseOrderProcess(arr, L, M) +
reverseOrderProcess(arr, M + 1, R) +
reverseOrderMerge(arr, L, M, R);
}
private static int reverseOrderMerge(int[] arr, int L, int M, int R) {
int p1 = L, p2 = M + 1;
int reversePair = 0;
int i = 0;
int[] help = new int[(R - L + 1)];
while (p1 <= M && p2 <= R){
reversePair += arr[p1] > arr[p2] ? (M + 1 - p1) : 0;
help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
}
while (p1 <= M){
help[i++] = arr[p1++];
}
while (p2 <= R){
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++){
arr[L + i] = help[i];
}
return reversePair;
}
@Test
public void testReverseOrder(){
int[] arr = generateRandomArray(100, 100);
arr = new int[]{1,3,2,3,1};
int sum = reverseOrder(arr);
System.out.println(sum);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
|
逆序对在Merge的时候也需要注意在左右两边的数相同的情况下，应该先放左边的（仅限于我这种做法），在判断两边相同的情况要先放哪边，一般是先放需要做长度运算的那边，也可以说需要被比较的那边（我的思路是用右边与左边比，如果右边的数比左边的数要小，那么左边的数之后的数都比右边的大，左边需要做下标运算，所以先放左边的）
快速排序
空间复杂度：O(logN) ~ O(N) – > O(logN)
public static void quickSort(int[] arr){
if(arr == null arr.length <= 1){
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int L, int R){
if(L < R){
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] p = partition(arr, L, R);
quickSort(arr, L, p[0] - 1);
quickSort(arr,p[1] + 1, R);
}
}
public static int[] partition(int[] arr, int L, int R){
int less = L - 1;
int more = R;
while (L < more){
if(arr[L] < arr[R]){
swap(arr, ++less, L++);
}else if(arr[L] > arr[R]){
swap(arr, --more, L);
}else {
L++;
}
}
swap(arr, more, R);
return new int[]{less + 1, more};
}
@Test
public void testQuickSort() {
int[] arr = generateRandomArray(100, 100);
quickSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
|
堆结构
堆在逻辑上是满二叉树的结构形式
堆分为大根堆和小根堆
大根堆：在一棵完全二叉树里，每一棵子树的最大值都是头节点的值
小根堆：在一棵完全二叉树里，每一棵子树的最小值都是头节点的值
完全二叉树的高度：log2(N + 1) N是节点数
如果我们把一个数组看作完全二叉树，那么假设一个节点的下标为index 那么这个节点的左子树头节点下标 index * 2 + 1 右子树头节点下标为 (index * 2 + 2) 父亲节点为 (index - 1) / 2
堆有两个重要的操作：
如果是大根堆，heapInsert的行为是寻找是否存在比待加入节点更小的父亲节点，如果存在，则做出交换，如果是小根堆结构，则heapInsert的行为是寻找是否存在比待加入节点更大的父亲节点，如果存在，则做出交换
如果是大根堆，heapify的作用是保证待加入的节点和其子节点相比，是最大的，如果不是，就需要交换，如果发送了交换，那么子树的结构发送了改变，后面的循环是保证子树是保持父节点最大，小根堆相反
heapInsert是用来添加数据，保证在添加数据之后，堆还是堆，时间复杂度是 O(logN)
heap是用来删除数据的，保证删除一个节点后，堆还是堆，时间复杂度是O(logN)
heapSize是堆的标识，代表数组中 0 ~ heapSize的区域是堆
public static void heapInsert(int[] arr, int index){
while (arr[index] > arr[(index - 1) / 2]){
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void heapify(int[] arr, int index, int heapSize){
int left = 2 * index + 1;
while (left < heapSize){
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if(largest == index){
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
|
堆排序
首先把数组的元素变成大根堆，然后把头节点与堆最后位置的数做交换，heapSize–,对头节点做heapify，让其还是大根堆，在把头节点与堆最后位置的数做交换，heapSize–，知道所有的数在正确的位置
public static void heapSort(int[] arr){
if(arr == null && arr.length < 2){
return;
}
for (int i = 0; i < arr.length; i++) { //O(N)
heapInsert(arr, i); // O(logN)
}
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0){ //O(N)
heapify(arr, 0 , heapSize); // O(logN)
swap(arr, 0, --heapSize); // O(1)
}
}
|
堆排序：时间复杂度是O(NlogN) 空间复杂度是O(1)
堆排序远远没有堆结构重要
假设 k = 7
根据要求，我们可以知道，下标 0 ~ 6 的小根堆结构的最小值一定可以找到，并且是数组的最小值，把0 ～ 6转换为小根堆，然后弹出0位置 加入 7位置，可以找到 1 ～ 7 位置上的最小值，把 1～7位置上的最小值放在1 上 弹出 1 ，加入8 ，周而复始，最后把最后几位依次做小根堆排序，就可以完成
Java语言自带了优先级队列（小根堆）
public static void sortedArrDistanceLessK(int[] arr, int k){
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0;
int i = 0;
for (;index <= Math.min(arr.length, k); index++){
heap.add(arr[index]);
}
for (; index < arr.length; i++, index++){
heap.add(arr[index]);
arr[i] = heap.poll();
}
while (!heap.isEmpty()){
arr[i++] = heap.poll();
}
}
|
通常比较简单的问题，只需要输入和弹出的题目，可以用Java自带的优先级队列
面试遇到的很多题，都会带有额外的需求，这种时候就需要自己手写堆，才能保证高效（比如，需要人为变更堆结构里面的一个节点的值，还要保证是堆结构，Java就需要一个个扫描，而自己写，就可以直接heapify）
不基于比较的排序，都是根据数据状况做的排序
简而言之，计数排序，就是根据需要排序的数据的范围，划分一个与范围相吻合的数组，比如需要排序的数据范围是[0-200]，那么就需要划分一个长度为201的数组arr，arr[i]代表的是，数据大小等于i的数据个数，遍历一遍数据后，就可以排好序，时间复杂度为Log(N) 空间复杂度是 Log(N)
public static void radixSort(int[] arr, int L, int R, int digit){
final int radix = 10;
int i = 0, j = 0;
int[] bucket = new int[R - L + 1];
for (int d = 1; d <= digit; d++){
int[] count = new int[radix];
for (i = L; i <= R; i++){
j = getDigit(arr[i], d);
count[j]++;
}
for (i = 1; i < radix; i++){
count[i] = count[i] + count[i - 1];
}
for (i = R; i >= L; i--){
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
for (i = L, j = 0; i <= R; i++, j++){
arr[i] = bucket[j];
}
}
}
private static int getDigit(int num, int radix) {
if(num < 0){
num = -num;
}
int tmp = (int) Math.pow(10, radix - 1);
if(num >= tmp){
num /= tmp;
return num % 10;
}else {
return 0;
}
}
public static int maxBits(int[] arr){
int max = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(arr[i], max);
}
int res = 0;
while (max != 0){
max /= 10;
res++;
}
return res;
}
|
排序算法总结
归并排序
时间复杂度：O(NlogN)
空间复杂度：O(N)
实现思路：
需要用到递归和二分的思想，先递归到最小的有序子数组，合并2个有序子数组，重复直到数组整体有序
实现代码：
public static void MergeSort(int[] arr, int L, int R){
if (arr == null L == R){
return;
}
int M = L + ((R - L) >> 1);
MergeSort(arr, L, M);
MergeSort(arr, M + 1, R);
Merge(arr, L, M, R);
}
public static void Merge(int[] arr, int L, int M, int R){
int[] help = new int[R - L + 1];
int p1 = L, p2 = M + 1, i = 0;
while (p1 <= M && p2 <= R){
help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
}
while (p1 <= M){
help[i++] = arr[p1++];
}
while (p2 <= R){
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
}
|
快速排序
时间复杂度：O(NlogN) 在最差的情况下会变成O(N^2)
空间复杂度：O(logN)
实现思路：从数组中随机的抽取一个数，用于标准，把数组按照这个标准数分为大于标准数，等于标准数，小于标准数，然后对大于标准数和小于标准数两个部分继续这个过程，直到数组整体有序
实现代码：
public static int[] partition(int[] arr, int L, int R){
int left = L - 1;
int right = R;
int temp = (int) ((R - L + 1) * Math.random() + L);
swap(arr, temp, R);
while (L < right){
if (arr[L] < arr[R]){
swap(arr, L++, ++left);
}
else if (arr[L] > arr[R]){
swap(arr, L, --right);
}
else{
L++;
}
}
swap(arr, right, R);
return new int[]{left + 1, right};
}
public static void QuickSort(int[] arr, int L, int R){
if(arr == null arr.length < 2){
return;
}
if(L < R){
int[] partition = partition(arr, L, R);
QuickSort(arr, L, partition[0] - 1);
QuickSort(arr, partition[1] + 1, R);
}
}
|
堆排序
时间复杂度：O(NlogN)
空间复杂度：O(1)
实现原理：把一个数组抽象为完全二叉树结构，保证这颗二叉树父节点永远大于子节点，交换父节点与数组最后的数，二叉树长度减少，重新保证父节点大于子节点，一直到二叉树为空
实现代码：
public static void heapify(int[] arr, int index, int heapSize){
int left = index * 2 + 1;
while (left < heapSize){
int largest = arr[left] < arr[left + 1] && left + 1 < heapSize ? left + 1 : left;
largest = arr[index] > arr[largest] ? index : largest;
if(index == largest){
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void heapInsert(int[] arr, int index){
while (arr[index] > arr[(index - 1) / 2]){
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void HeapSort(int[] arr){
if(arr == null arr.length < 2){
return;
}
for(int i = 0; i < arr.length; i++){
heapInsert(arr, i);
}
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0){
heapify(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
|
稳定性：相同的待排序对象在排序完成之后相对顺序保持不变的性质
实际使用一般选择快速排序，虽然指标一样，但是常数项经过实验需要花费的时间是最低的
堆排序：对于空间有额外要求的情况下使用
归并排序：对于稳定性有额外要求的情况下使用
基于比较的算法：时间复杂度低于O(NlogN) 目前没找到
基于比较的算法：空间复杂度低于O(N) 并且还具有稳定性的算法，目前没找到
在范围小的时候使用插入排序，利用了插入排序，常数时间低的优势
