TalkGo 算法之美第一期

tiecheng 收录于算法

2020-09-18 约 1023 字预计阅读 3 分钟次阅读

本文介绍 TalkGo 算法之美第一期题解

一、前言

talkgo地址

题目一

输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得他们的和正好是 S，如果有多对数字的和等于 S，输出两个数的乘积最小的。

LeetCode

题目二

一个有序数组，从随即一位截断，把前段放在后边，如 4 5 6 7 1 2 3 求中位数

二、解析

2.1 题目一

思考：

因为递增，负数和正数的情况一致，一组数据最小的值越小则乘积也越小
如果出现重复数字，也和正常情况一样的处理

2.1.1 处理方式

暴力法

 1func TwoSum2For(sum int, array []int) []int {
 2	b, arr := checkArray(array)
 3
 4	if !b {
 5		return arr
 6	}
 7
 8	for i := 0; i < len(array); i++ {
 9		for j := len(array) - 1; j > i; j-- {
10			if sum == array[i]+array[j] {
11				return []int{array[i], array[j]}
12			}
13		}
14	}
15
16	return []int{}
17}

直接两层 for 循环，如何匹配到数组两个位置的值等于传入的和，则直接返回。此方法简单易懂，可读性高。

时间复杂度 O(n^2)
空间复杂度 O(1)

缓存法

 1// TwoSumMap map 缓存法
 2func TwoSumMap(sum int, array []int) []int {
 3	b, arr := checkArray(array)
 4
 5	if !b {
 6		return arr
 7	}
 8
 9	// 通过 map 缓存数据
10	cache := make(map[int]int, len(array))
11	for i := range array {
12		cache[array[i]] = i
13	}
14
15	// 返回值在数组中的位置
16	for i := range array {
17		// 通过减法找到另一个值，直接去 map 查找
18		if _, ok := cache[sum-array[i]]; ok {
19			return []int{array[i], sum - array[i]}
20		}
21	}
22
23	return []int{}
24}

借助 map 把数组的值进行了缓存，用到了加法变减法的思路根据 hash 算法可以直接找到对应的另一个值是否存在。这个写法很直观，比第一种暴力法更加简单，建议平日小数量的时候直接用就行。

时间复杂度 O(n)
空间复杂度 O(2n)

双指针法

 1func TwoSum2Point(sum int, array []int) []int {
 2	b, arr := checkArray(array)
 3
 4	if !b {
 5		return arr
 6	}
 7
 8	left, right := 0, len(array)-1
 9	for left < right {
10		s := array[left] + array[right]
11		if sum == s {
12			return []int{array[left], array[right]}
13		} else if sum > s {
14			left++
15		} else {
16			right--
17		}
18	}
19
20	return []int{}
21}

双指针法是字符查找的时候经常使用的方法，在数据量大的场景下会比较有优势。它的写法代码看着比较高级。

2.2 题目二

思考：

先要回想下什么是中位数，奇偶的处理方式是不一样的
找到截断的位置，计算中位数涉及到的数字的 index

偶数中位数的一个例子：

中位数在线学习

代码：

 1// MiddleNum 算中位数
 2func MiddleNum(nums []int) (float32, error) {
 3	l := len(nums)
 4	if l <= 0 {
 5		return 0, illegalArray
 6	}
 7
 8	if l == 1 {
 9		return float32(nums[0]), nil
10	} else if l == 2 {
11		return float32((nums[0] + nums[1]) / 2), nil
12	}
13
14	p := Point(nums)
15
16	if isEven(l) {
17		target1 := l / 2
18		target2 := l/2 + 1
19		return (float32(nums[Position(l, p, target1)]) + float32(nums[Position(l, p, target2)])) / 2, nil
20	} else {
21		return float32(nums[Position(l, p, (l+1)/2)]), nil
22	}
23}
24
25// Point 得到拐点
26func Point(nums []int) int {
27	if len(nums) < 3 {
28		return 0
29	}
30
31	n, flag := nums[0], -1
32
33	for i := 1; i < len(nums); i++ {
34		cf := -1
35		c := nums[i]
36		if c < n {
37			cf = 1 // 降
38		} else if c > n {
39			cf = 0 // 升
40		}
41
42		if flag >= 0 && cf >= 0 && cf != flag {
43			return i
44		}
45
46		n = c
47		if cf >= 0 {
48			flag = cf
49		}
50	}
51
52	return 0
53}
54
55// Position 获取位置
56func Position(l, p, t int) int {
57	if l-p > t {
58		return p + t - 1
59	} else {
60		return t + p - l - 1
61	}
62}

代码

题1

题2

目录