该文章基于B站视频：一周刷爆LeetCode，算法大神左神…
1，时间复杂度
常数时间的操作
一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。具体
来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，
进而总结出常数操作数量的表达式。
在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那
么时间复杂度为O(f(N))。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行
时间（当时间复杂度相同，或已知数据量时），也就是“常数项时间”，以下为举例：
O()：是指最差情况下算法的时间复杂度。
package Day1;
public class Test {
public static void process1(){
int N=1000;
int a=0;
for (int i = 0; i < N; i++) {
a=2+5;
a=4*7;
a=6*8;
}
}
public static void process2(){
int N=1000;
int a=0;
for (int i = 0; i < N; i++) {
a=3|6;
a=3&4;
a=4^785;
}
}
public static void main(String[] args) {
Test test=new Test();
process1();
process2();
}
}
无论系数多大，都跟系数没有关系，无论低阶项多大都与其无关，因为在数据量大到一定规模时，一定是高阶项
的影响更大
2，选择排序：
选择排序是最为简单的排序方式，依次选取最小值向前填充直到排序完毕
时间复杂度O(N^2)，额外空间复杂度O(1)
参考代码：
package Day1;
public class SelectionSort {
public static void SelectionSort(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++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
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 = new int[5];
for (int i = 0; i < arr.length; i++) {
arr[i] = arr.length - i;
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
SelectionSort(arr);
System.out.println(" SelectionSort(arr);");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
3，冒泡排序
在数组中依次比较相邻两个位置，数据大的位置排到右边，排序完毕后再次从数组开头排序，直到每次比较两个位置时数据大的都在右边。
时间复杂度O(N^2)，额外空间复杂度O(1)
参考代码：
package Day1;
public class BubbleSort {
public static void BubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {//去除无效和无法排序的数组
return;
}
for (int e = arr.length-1; e >0 ; e--) {
for (int i = 0; i < e; i++) {
if (arr[i]>arr[i+1]){
swap(arr,i,i+1);
}
}
}
}
//交换arr的i位置和j位置上的值,异或运算
public static void swap(int[] arr,int i,int j) {
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}
public static void main(String[] args) {
int[] arr = new int[5];
for (int i = 0; i < arr.length; i++) {
arr[i] = arr.length - i;
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
BubbleSort(arr);
System.out.println(" BubbleSort(arr);");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
3，异或运算
指不同为1，相同为0，也可以理解为二进制的无进位相加；
原理：
0^N=N;
N^N=0;
//交换arr的i位置和j位置上的值,异或运算
public static void swap(int[] arr,int i,int j) {
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}
注意：该方法的前提是arr[i]在内存中的位置必须和arr[j]的位置不同
如当i=j时，该位置的值会变成0；
3.1面试题举例：
1， 已知一个数组中只有一组数出现了奇数次其他数都是偶数次，求该出现奇数次的数
package Day1;
public class Test {
public static void main(String[] args) {
int []arr=new int[]{2,1,3,2,1,3,3};
int eor=0;
for (int i = 0; i < arr.length; i++) {
eor=eor^arr[i];//相当于偶数次各自异或得到的结果是奇数次的数
}
System.out.println(eor);//结果为3
}
}
2， 已知一个数组中只有两组数出现了奇数次其他数都是偶数次，求该出现奇数次的数
package Day1;
public class Test {
public static void main(String[] args) {
int[] arr = new int[]{2, 1, 3, 2, 1, 3, 3, 4};
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor = eor ^ arr[i];
}
//eor=a^b;
//eor!=0
//eor必然有一个位置上是1
int rightOne = eor & (~eor + 1);//提取出最右侧的1
int eor1=0;
for (int cur:arr){
if((cur&rightOne)==1){
eor1^=cur;
}
}
System.out.println(eor1+" "+(eor^eor1));
}
}
4，插入排序
从0~0位，0到1位，0到2位…依次从小到大排序，其中每一次最大位与它前面位置进行数据比较，当其小于前位时进行交换，前位再与其前面的位置进行比较，直到该数值不小于前位的数值：
跟数据状况无关，执行的次数是一样的
时间复杂度O(N^2)，额外空间复杂度O(1)
参考代码：
package Day1;
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--) {//到i位置时，做到了0~i-1有序，此时j为0~i-1最大的数，
swap(arr,j,j+1);
}
}
}
//交换arr的i位置和j位置上的值,异或运算
public static void swap(int[] arr,int i,int j) {
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}
public static void main(String[] args) {
int[] arr = new int[5];
for (int i = 0; i < arr.length; i++) {
arr[i] = arr.length - i;
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
insertionSort(arr);
System.out.println(" insertionSort(arr);");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
5，二分法
1）在一个有序数组中，找某个数是否存在
2）在一个有序数组中，找>=某个数最左侧的位置
3）局部最小值问题
6，对数器
对数器的概念和使用
1，有一个你想要测的方法a
2，实现复杂度不好但是容易实现的方法b
3，实现一个随机样本产生器
4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。
5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者
方法b
6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确