01-复杂度、排序、二分、异或.md

[TOC]
#  1 时间复杂度、空间复杂度、排序、异或运算
##  1.1 时间复杂度
- 常数时间操作：
1. 算数运算：`+` `-` `*` `/`
2. 位运算：`>>`（带符号右移动）、 `>>>`（不带符号右移动） 、 `<<`、 `|` 、`&` 、`^`

> 带符号就是最高位补符号位，不带符号就是最高位补0

3. 赋值操作：比较，自增，自减操作
4. 数组寻址等

> 总之，执行时间固定的操作都是常数时间的操作。反之执行时间不固定的操作，都不是常数时间的操作

- 通过基本动作的常数时间，推导时间复杂度

> 对于双层循环来说，n*（常数）+ (n-1)*(常数)+ ... + 2*(常数) + 1*（常数） => 推导出

```math
y = an^2 + bn + c
```

> 忽略掉低阶项，忽略掉常数项，忽略掉高阶项的系数，得到时间复杂度为n^2

### 1.1.1 排序操作
---
#### 1.1.1.1 选择排序
```Go
package main

import "fmt"

func main() {
	arr := []int{1, 4, 5, 8, 3, 1, 0, 22, 53, 21}
	selectionSort(arr)
	fmt.Println(arr)
}

// 选择排序
func selectionSort(arr []int) {
	if len(arr) == 0 || len(arr) < 2 {
		return
	}

	// 在i到n-1的位置依次处理, i从0开始
	for i := 0; i < len(arr)-1; i++ {
		minIndex := i
		// 寻找当前剩余元素的最小值放在当前位置
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		swap(arr, i, minIndex)
	}
}

func swap(arr []int, a, b int) {
	tmp := arr[a]
	arr[a] = arr[b]
	arr[b] = tmp
}
```
---
#### 1.1.1.2 冒泡排序
```Go
// 冒泡排序
func bubbleSort(arr []int) {
	if len(arr) == 0 || len(arr) < 2 {
		return
	}

	// 外循环从最大位置开始处理，形成冒泡的效果
	for i := len(arr) - 1; i > 0; i-- {
		// 内循环的一轮次，搞定外循环的一个位置。
		for j := 0; j < i; j ++ {
			if arr[j] > arr[i] {
				swap(arr, i, j)
			}
		}
	}
}
```
---
#### 1.1.1.3 插入排序
```Go
// 选择排序
func insertionSort(arr []int) {
	if len(arr) == 0 || len(arr) < 2 {
		return
	}

	// 类比打扑克牌
	for i := 1; i < len(arr); i++ {
		// 每一轮内循环，与前面的元素来一轮比较，达到的效果是最小元素经过一轮内循环总能放到0位置
		for j := i - 1; j >=0 ; j-- {
			if arr[j] > arr[j + 1] {
				swap(arr, j, j + 1)
			}
		}
	}
}
```

> 插入排序和前面两种排序的不同是在于，插入排序跟数组初始顺序有关，在初始有序的情况下，有可能时间复杂度为O(N),有可能为O(N ^2)，但是我们估计时间复杂度要按照最差的情况来估计，所以插入排序的时间复杂度仍然O(N ^2)

## 1.2 空间复杂度

申请有限几个变量，和样本量n没关系，就是空间复杂度O(1)，如果要开辟一个空间数组和样本量n是一样大，用来支持我们的算法流程那么O(N)。反之用户就是要实现数组拷贝，我们开辟一个新的n大小数组用来支撑用户的需求，那么仍然是O(1)


## 1.3 常数项时间复杂度

如果两个相同时间复杂度的算法要比较性能，这个时候需要比较单个常数项时间，对能力要求较高，没有意义，不如样本量试验实际测试来比较

## 1.4 算法最优解

我们认为最优解的考虑顺序是，先满足时间复杂度指标，再去使用较少的空间。一般来说，算法题，ACM等不会卡常数项时间

## 1.5 常见时间复杂度
> 依次从好到坏 O(1) -> O(logN) -> O(N) -> O(N*logN) -> O(N^2) -> O(N^3) ... -> O(N!)

## 1.6 算法和数据结构脉络

1. 知道怎么算的算法
2. 知道怎么试的算法(递归)

## 1.7 认识对数器

1. 准备你想要测试的方法a
2. 实现一个复杂度不好，但是容易实现的方法b
3. 实现一个随机样本产生器
4. 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
5. 如果有一个随机样本使得对比结果不一致，打印样本进行人工干预，改对方法a和方法b
6. 当样本数量很多，测试对比依然正确，可以确定方法a已经正确

## 1.8 认识二分法

1. 在一个有序数组中，找某个数是否存在

> 二分查找值，基于有序数组，算法复杂度为二分了多少次，O(log2N)可以写成O(logN)

```Go
// 有序数组二分查找
func exist(arr []int, target int) bool {
	if len(arr) == 0 {
		return false
	}

	var L = 0
	var R = len(arr) - 1
	var mid = 0
	for L < R {
		// 防止整数越界
		mid = L + (R - L) / 2
		if arr[mid] == target {
			return true
		} else if arr[mid] < target { // mid位置已经比较过，L置为mid+1
			L = mid + 1
		} else if arr[mid] > target { // mid位置已经比较过，R置为mid-1
			R = mid - 1
		}
	}
	return arr[L] == target
}
```

2. 在一个有序数组中，找>=某个数最左侧的位置

> 122222333578888999999 找大于等于2最左侧的位置

```Go
// 在一个有序数组上，找到大于等于value的最左位置
func nearestLeftIndex(arr []int, value int) int {
	L := 0
	R := len(arr) - 1
	index := -1
	for L <= R {
		mid := L + (R - L) / 2
		// 当前中间位置大于value，寻找大于value最左位置，缩小右边界，继续寻找
		if arr[mid] >= value {
			index = mid
			R = mid - 1
		} else {
			L = mid + 1
		}
	}
	return index
}
```

3. 在一个有序数组中，找小于等于某个数最右侧的位置

```Go
// 在一个有序数组上，找到小于等于value的最右位置
func nearestRightIndex(arr []int, value int) int {
	L := 0
	R := len(arr) - 1
	index := -1
	for L <= R {
		mid := L + (R - L) / 2
		if arr[mid] <= value {
			index = mid
			L = mid + 1
		} else {
			L = mid - 1
		}
	}
	return index
}
```

## 1.9 认识异或运算

异或运算：相同为0，不同为1

同或运算：相同为1， 不同为0，不掌握

>上述规则不容易记住，异或运算就记成无进位相加：比如十进制6异或7，就理解为110和111按位不进位相加,得到001

1.  所以 0^N = N ，  N^N = 0
2.  异或运算满足交换律和结合律,所以A异或B异或C = A异或(B异或C) = (A异或C)异或B

**题目一：如何不用额外变量就交换两个数**

```shell
# 三步操作，实现交换ab的值
# a = x b = y两个数交换位置

a = a ^ b # 第一步操作，此时 a = x^y , b=y
b = a ^ b # 第二步操作，此时 a = x^y , b = x^y^y => b = x^0 => b = x
a = a ^ b # 第三步操作，此时 a = x^y^x, b = x, a=> x^x^y => a=y
```

```Go
// IsoOr 异或交换数据
func IsoOr()  {
	a := 3
	b := 4
	a = a ^ b
	b = a ^ b
	a = a ^ b
	fmt.Println(a)
	fmt.Println(b)

	arr := []int{3, 1, 100}
	IsoOrSwap(arr, 0, 3)
	fmt.Println(arr)

	// i和j指向同一块内存，这种位运算交换变量的方法就不可行了。
	IsoOrSwap(arr, 0, 0)
}

func IsoOrSwap(arr []int, i, j int)  {
	arr[i] = arr[i] ^ arr[j]
	arr[j] = arr[i] ^ arr[j]
	arr[i] = arr[i] ^ arr[j]
}
```

> 注意，如果a和b指向同一块内存，该交换方法不可行

---

**题目二：一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数**

> [2,2,1,3,2,3,2,1,1] 数组中存在四个2，两个3，三个1，定义一个常量等于0，分别对该数组中的数遍历一遍进行异或，最后，该变量等于多少，那么奇数的值就是多少。因为异或运算满足交换和结合律

```Go
package main

import "fmt"

func main() {
	arr := []int{2, 2, 1, 3, 2, 3, 2, 1, 1}
	flag := 0
	for i := 0; i < len(arr); i++ {
		flag = flag ^ arr[i]
	}

	fmt.Println(flag)
}
// 打印 1
```

---

**题目三：怎么把一个int类型的数，提取出最右侧的1来**

> n与上（n取反加1）即可 => N & ( (~N)+1 )

例如一个int数n：00000000 00000000 00001010 01000000

先对n取反得到：  11111111 11111111 11110101 10111111

再加1得到：     11111111 11111111 11110101 11000000

再与原n做与运算：11111111 11111111 11110101 11000000 & 00000000 00000000 00001010 01000000

得到：00000000 00000000 00000000 01000000

---

**题目四：一个数组中有两种不相等的数出现了奇数次，其他数出现了偶数次，怎么找到并打印这两种数**

思路：定义一个常量flag = 0，分别对该数组每个数异或，最终结果为a异或b，其中a和b就是这两个奇数，由于a!=b所以a异或b不等于0，即flag的值某一位上一定为1（有可能不止一个1随便选一个例如第八位），用该位做标记对原有数组的数进行分类，那么a和b由于第八位不相同一定被分开，再定义常量flag' = 0分别对第八位为0的数异或，那么得到的值，就是a和b其中一个，由于之前flag = a异或b，那么在用flag和flag'异或，就是另外一个值。一般来说，随便找一个1我们就找最右侧的那个1，如题目三


```Go
package main

import "fmt"

func main() {
	arr := []int{4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2}
	printNum(arr)
}

func printNum(arr []int) {
	flag := 0
	// 经过循环处理，flag等于这两个不相等的且出现奇数次的异或结果；a ^ b
	for i := 0; i < len(arr); i++ {
		flag = flag ^ arr[i]
	}

	// 由于a != b 所以flag不为0。则flag的二进制位上一定存在1，选最后一位的1
	// 选取办法是，用flag 与 自身取反加1的结果做与运算
	rightOne := flag & ((^flag) + 1)
	onlyOne := 0
	// 经过这层循环的筛选，onlyOne等于a或者b其中的一个
	for j := 0; j < len(arr); j++ {
		if arr[j]&rightOne != 0 {
			onlyOne = onlyOne ^ arr[j]
		}
	}
	result1 := onlyOne
	result2 := flag ^ onlyOne
	// result1和result2就是数组中不相等的且为奇数的两个未知数a、b
	fmt.Println(result1)
	fmt.Println(result2)
}
```