# Array
# No.1 两数之和
func twoSum(nums []int, target int) []int { | |
m := make(map[int]int) | |
for i:=0;i<len(nums);i++{ | |
x := target - nums[i] | |
if _, ok:= m[x];ok{ | |
return []int{m[x], i} | |
} | |
m[nums[i]] = i | |
} | |
return nil | |
} |
这道题主要是使用了 map 来做了结果保存，因为 map 的查询复杂度可以近似为 O (1)，所以这道题的时间复杂度为 O (n)，空间复杂度为 O (n)。
总结：用 map 来保存之前结果，并且优化查询的复杂度。
# No.2 二分搜索
// 二分查找非递归实现 | |
func binarySearch(target int64, nums []int64) int { | |
left := 0 | |
right := len(nums) | |
for left <= right { | |
mid := left + (right - left) / 2 | |
if target == nums[mid] { | |
return mid | |
} | |
if target > nums[mid] { | |
left = mid + 1 | |
continue | |
} | |
if target < nums[mid] { | |
right = mid - 1 | |
continue | |
} | |
} | |
return -1 | |
} |
奇偶性通过按位与来判断
a & 1 == 1 : 判断是否是奇数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { | |
if len(nums1) > len(nums2) { | |
return findMedianSortedArrays(nums2, nums1) | |
} | |
m, n := len(nums1), len(nums2) | |
left, right := 0, m | |
median1, median2 := 0, 0 | |
for left <= right { | |
i := (left + right) / 2 | |
j := (m + n + 1) / 2 - i | |
nums_im1 := math.MinInt32 | |
if i != 0 { | |
nums_im1 = nums1[i-1] | |
} | |
nums_i := math.MaxInt32 | |
if i != m { | |
nums_i = nums1[i] | |
} | |
nums_jm1 := math.MinInt32 | |
if j != 0 { | |
nums_jm1 = nums2[j-1] | |
} | |
nums_j := math.MaxInt32 | |
if j != n { | |
nums_j = nums2[j] | |
} | |
if nums_im1 <= nums_j { | |
median1 = max(nums_im1, nums_jm1) | |
median2 = min(nums_i, nums_j) | |
left = i + 1 | |
} else { | |
right = i - 1 | |
} | |
} | |
if (m + n) % 2 == 0 { | |
return float64(median1 + median2) / 2.0 | |
} | |
return float64(median1) | |
} | |
func max(x, y int) int { | |
if x > y { | |
return x | |
} | |
return y | |
} | |
func min(x, y int) int { | |
if x < y { | |
return x | |
} | |
return y | |
} |
这道题要求给出两个以及有序的数组，求这两个数组合并后的中位数。
思路，中位数实际上起到的就是划分作用，那我只要说找到这么一个划分方法就行了，我看了半天才看懂，哎，好久没写算法题了。。。
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
参考：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
