1.寻找两个有序数组的中位数
这道题是个困难类的题。。。
先来个简单解决办法：暴力解,将两个数组排序后找到中位数，时间复杂度为O(m+n)
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
len1 := len(nums1)
len2 := len(nums2)
if len1 == 0 {
if len2%2 == 0 {
return float64(nums2[len2/2]+nums2[len2/2-1]) / 2.0
} else {
return float64(nums2[len2/2])
}
}
if len2 == 0 {
if len1%2 == 0 {
return float64(nums1[len1/2]+nums1[len1/2-1]) / 2.0
} else {
return float64(nums1[len1/2])
}
}
sum := len1 + len2
i, j := 0, 0
temp := []int{}
for i < len1 || j < len2 {
if i == len1 {
temp = append(temp, nums2[j:]...)
break
}
if j == len2 {
temp = append(temp, nums1[i:]...)
break
}
if nums1[i] <= nums2[j] {
temp = append(temp, nums1[i])
i++
} else {
temp = append(temp, nums2[j])
j++
}
}
if sum%2 == 0 {
return float64(temp[sum/2]+temp[sum/2-1]) / 2.0
} else {
return float64(temp[sum/2])
}
}
第二种方法，不必使用临时数组，但是思路一致
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
len1 := len(nums1)
len2 := len(nums2)
targetRight := -1
targetLeft := -1
i, j := 0, 0
for now := 0; now <= (len1 + len2) / 2; now++ {
targetLeft = targetRight
if (i < len1) && (j >= len2 || nums1[i] < nums2[j]) {
targetRight = nums1[i]
i++
} else {
targetRight = nums2[j]
j++
}
}
if (len1 + len2) % 2 == 0 {
return float64(targetLeft + targetRight) / 2.0
} else {
return float64(targetRight)
}
}
第三种就是重头戏了，二分查找,这其实就是查询两个有序数组合并之后的第K个数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
len1 := len(nums1)
len2 := len(nums2)
leftK := 0
rightK := 0
if (len1 + len2) % 2 == 0 {
leftK = (len1 + len2) / 2
rightK = leftK + 1
} else {
leftK = (len1 + len2) / 2 + 1
rightK = (len1 + len2) / 2 + 1
}
return (getK(nums1, 0, len1 - 1, nums2, 0, len2 - 1, leftK) + getK(nums1, 0, len1 - 1, nums2, 0, len2 - 1, rightK)) / 2.0
}
func getK(t1 []int, start1, end1 int, t2 []int, start2, end2 int, k int) float64 {
len1 := end1 - start1 + 1
len2 := end2 - start2 + 1
if len1 > len2 {
return getK(t2, start2, end2, t1, start1, end1, k)
}
if len1 == 0 {
return float64(t2[start2+k-1])
}
if k == 1 {
return float64(min(t1[start1], t2[start2]))
}
left := start1 + min(k/2, len1) - 1
right := start2 + min(k/2, len2) - 1
if t1[left] < t2[right] {
return getK(t1, left+1, end1, t2, start2, end2, k-(left-start1+1))
} else {
return getK(t1, start1, end1, t2, right+1, end2, k-(right-start2+1))
}
return -1.0
}
2.求Pow(x, n)
快速幂法
func myPow(x float64, n int) float64 {
if n < 0 {
return myPow(1/x, -n)
}
return fastPow(x, n)
}
func fastPow(x float64, n int) float64 {
if n == 0 {
return 1.0
}
half := fastPow(x, n / 2)
if n % 2 ==0 {
return half * half
} else {
return half * half * x
}
}
3.给定一个二维数组，数组每一行有序并且后一行的第一个元素比上一行的最后一个元素大，求是否存在某个元素
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
start := 0
end := len(matrix) * len(matrix[0]) - 1
for start <= end {
mid := start + (end - start) / 2
temp := matrix[mid / len(matrix[0])][mid % (len(matrix[0]))]
if temp == target {
return true
} else if temp > target {
end = mid - 1
} else {
start = mid + 1
}
}
return false
}
4.给定一个翻转数组，求最小值
func findMin(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
left := 0
right := len(nums) - 1
if nums[right] > nums[left] {
return nums[left]
}
for left <= right {
mid := left + (right - left) / 2
if nums[mid] > nums[mid + 1] {
return nums[mid + 1]
}
if nums[mid] < nums[mid - 1] {
return nums[mid]
}
if nums[mid] > nums[left] {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
第二种解法：如果一个数组最左边小于最右边，那么这个数组是有序并且最小值是最左边
func search(nums, left, right) int {
if nums[right] > nums[left] {
return nums[left]
}
mid := left + (right - left) / 2
return min(search(nums, left, mid), search(nums, mid + 1, right))
}
变种：数组如果有重复元素
func findMin(nums []int) int {
left := 0
right := len(nums) - 1
for left <= right {
mid := left + (right - left) / 2
if nums[mid] < nums[right] {
right = mid
} else if nums[mid] > nums[right]{
left = mid + 1
} else {
right = right - 1
}
}
return nums[left]
}
这里使用right而不使用left比较是因为寻找最小值，存在[1,2,3,4,5]，[2,3,4,5,1]这两种情况，如果使用left则无法分辨；而相等时存在[1,1,1,3,1]这种情况，所以只需要保留一个mid就可以了，right缩小一位。
5.给定一个升序数组，求出满足两数之和为target的两个数的下标
双指针法：
func twoSum(numbers []int, target int) []int {
left := 0
right := len(numbers) - 1
for left < right {
sum := numbers[left] + numbers[right]
if sum == target {
return []int{left+1, right+1}
} else if sum > target{
right --
} else {
left ++
}
}
return []int{}
}
6.给定一个有序数组，求出和大于等于target的最小子数组
双指针法：
func minSubArrayLen(s int, nums []int) int {
sum := 0
left := 0
right := 0
res := 9999
for right < len(nums) {
sum += nums[right]
right ++
for sum >= s {
res = Min(res, right - left)
sum -= nums[left]
left ++
}
}
if res == 9999 {
res = 0
}
return res
}
7.给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间,求重复的那个数字
快慢指针，先找环，后找入口
func findDuplicate(nums []int) int {
slow := 0
fast := 0
for {
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast {
break
}
}
find := 0
for {
find = nums[find]
slow = nums[slow]
if slow == find {
return find
}
}
}
