时间复杂度

时间复杂度是常数操作地指标
数组：偏移量直接寻址搞定
链表：需要一个一个地去找，不能通过偏移量去找
常数操作地表达式，不要低阶项，也不要高阶项地系数，只保留高阶项，就是时间复杂度
复杂度越小越好
当复杂度一致地时候，需要拼常数项或者直接用程序运行走一把

func pro1() {
	n := 1000
	for i := 0; i < n; i++ {
		n = 1 + 1
		n = 1 * 1
		n = 3 * 3
	}
}
func pro2() {
	n := 1000
	for i := 0; i < n; i++ {
		n = 1 | 1
		n = 1 & 1
		n = 3 ^ 3
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

常数操作

跟数据量无关地，固定时间地东西
加减乘除
数组
位运算

非常数操作

跟数据量有关地
底层api
链表

额外空间复杂度

额外有限几个变量就可以完成，复杂度为O(1)
如果需要开辟数组，则为O(n)

选择排序

每次在未排序地数组中找到一个最小的，与当前数交换位置

func selectsort(arr []int) []int {
	temp := len(arr)
	if temp < 2 || arr == nil { // 写程序前先考虑过滤杂项
		return nil
	}
	for i := 0; i < temp; i++ {
		minindex := i
		for j := i + 1; j < temp; j++ {
			if arr[minindex] > arr[j] {
				minindex = j
			}

		}
		arr[minindex], arr[i] = arr[i], arr[minindex]
	}
	return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：O(n^2)
一个for循环为o(n)，嵌套for循环相乘即可
空间复杂度：O(1)
为了实现此算法，额外定义了temp,i,j,minindex，使用的空间有限，所以为O(1)

冒泡排序

每一次当前值跟后一个值做对比，当前值大于后一个值，就交换位置，简称沉底

func bubblesort(arr []int) []int {
	temp := len(arr)
	if temp < 1 || arr == nil {
		return nil
	}
	for i := 0; i < temp; i++ {
		for j := 0; j < temp-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：一共需要n次循环，一共需要比较n次，所以时间复杂度为O(n^2)
空间复杂度：有限的几个变量，则为O(1)

位运算

无进位相加
能用位运算的就用位运算，别问为什么


a和b在内存里是两块独立的区域
a = 10
b = 10
查看a与b的地址

	a := 10
	b := 10
	fmt.Println(&a, &b) // 0xc0000160a8 0xc0000160c0

// 思考
	a := 10
	b := 10
	fmt.Println(&a, &b) //0xc0000aa078 0xc0000aa090
	a, b = b, a
	fmt.Println(&a, &b) //0xc0000aa078 0xc0000aa090
1
2
3
4
5
6
7
8
9
10

一种数

func printOddTimesNum1(arr []int) int {
	value := 0
	for _, eor := range arr {
		value ^= eor
	}
	return value
}

func main() {
	nums := []int{1, 3, 3, 2, 2, 6, 6}
	fmt.Println(printOddTimesNum1(nums))
}
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：O(n)
空间负载的：O(1)

两种数

func printOddTimesNum2(arr []int) (int, int) {
	value := 0
	for _, eor := range arr { //首先把这两个数找到
		value ^= eor
	}
	// 取出一个数最右侧的1 将这个数&这个数取反在加1
	rightone := value & (-value + 1)
	for _, eor := range arr {
		if (eor & rightone) != 0 { // 将尾数是1的拿出来
			rightone ^= eor // 此操作可以拿到其中的一个数
		}
	}
	return value ^ rightone, rightone
}

func main() {
	nums := []int{1, 3, 3, 2, 2, 6, 6, 9}
	fmt.Println(printOddTimesNum2(nums))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：O(n + n) = O(n)
空间复杂度：O(1)

位运算要看八位

插入排序

每一次向当前值往前到第一个，将小的值放在前面

daily practice

二分查找:

func search(nums []int, target int) int {
	if len(nums) < 1 || nums == nil {
		return -1
	}
	L := 0
	R := len(nums) - 1
	mid := 0
	for L <= R {
		mid = L + (R-L)>>1
		if nums[mid] > target {
			R = mid - 1
		} else if nums[mid] < target {
			L = mid + 1
		} else if nums[mid] == target {
			return mid
		}
	}
	return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：每一次都折半查找，比如一共查找八次，则就是2^n = 8，求n使用logn即可搞定
空间复杂度：寥寥几个变量，O(1)

移除元素:

package main

import "fmt"

func removeElement1(nums []int, val int) int {
	temp := len(nums)
	count := temp
	newval := temp
	for _, eor := range nums {
		if val == eor {
			temp--
		} else {
			nums = append(nums, eor)
			count += 1
		}
	}
	nums_count := len(nums[newval:])
	for key, eor := range nums[newval:] {
		nums[key] = eor
		if nums[key] == val {
			nums[key] = eor
		}
	}
	fmt.Println(nums)
	nums = nums[:nums_count]
	return temp
}
func removeElement2(nums []int, val int) int {
	temp := len(nums)
	// count := temp
	cc := temp
	for _, eor := range nums {
		if val != eor {
			nums = append(nums, eor)
			cc += 1
		}
	}
	for key, eor := range nums {
		if (key + temp) < cc {
			eor = nums[key+temp]
		} else {
			eor = 0
		}
		fmt.Println(eor)
	}
	fmt.Println(nums)
	return cc
}

func removeElement(nums []int, val int) int {
	left := 0
	for _, v := range nums { // v 即 nums[right]
		if v != val {
			nums[left] = v
			left++
		}
	}
	fmt.Println(nums)
	return left
}

func main() {
	nums := []int{0, 1, 2, 2, 3, 0, 4, 2}
	val := 2
	fmt.Println(removeElement(nums, val))
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

刚开始思路就想的太傻了，刚开始是这样想的

把与val不相同的一直往后面放，然后在将后面的跟前面的交换位置
直到我看了一眼答案，惊为天人

有序数组的平方: