内容简介:本篇文章是对leetcode中在大家读题的时候不知有没有注意两个小细节“O(log(m+n))”和“Sorted Arrays”。经常刷题的同学可能很容易想到这个不就是二分查找吗。所以我们撇开这题不谈,先看看二分查找。如果确定是长度很短的数组,我建议大家直接遍历就行了。但是在项目中这么理想的情况很少存在,我们经常需要处理长度特别长的数组,这时候遍历可能就有点吃不消了。于是一种优化的方法自然成了我们追求的目标,这里给出二分查找的方法。
本篇文章是对leetcode中 Median Of Two Sorted Arrays 解法的整理。
image.png
二分查找
在大家读题的时候不知有没有注意两个小细节“O(log(m+n))”和“Sorted Arrays”。经常刷题的同学可能很容易想到这个不就是二分查找吗。所以我们撇开这题不谈,先看看二分查找。
给定一个有序数组a = [1,3,5,7,9,10,11,13,14,15],如果快速找到数字11的位置。
如果确定是长度很短的数组,我建议大家直接遍历就行了。但是在项目中这么理想的情况很少存在,我们经常需要处理长度特别长的数组,这时候遍历可能就有点吃不消了。于是一种优化的方法自然成了我们追求的目标,这里给出二分查找的方法。
上面给出的数组是有序的,那么如果把数组在中间一分为二,那是不是意味着我们只需要对左侧数组的最大值(最后一个数字)和右侧数组的最小值(第一个数组)比较,就可以判断目标值11在左半边还是右半边。
采用相同的方法在确定的小数组中继续一分为二并判断,直到找到目标值。
这就是二分查找,来张图演示一下:
image.png
Golang代码(非递归):
func BinarySearch(arr []int, target int)(index int) { leftIndex, rightIndex := 0, len(arr) - 1 for { if leftIndex > rightIndex { // 未找到的退出条件 index = -1 break } middleIndex := (leftIndex + rightIndex) / 2 if arr[middleIndex] == target { // 找到的退出条件 index = middleIndex break } else if arr[middleIndex] > target { //取左侧一半数组 rightIndex = middleIndex - 1 } else { //取右侧一半的数组 leftIndex = middleIndex + 1 } } return }
Golang代码(递归):
func BinarySearch(arr []int, target int)(index int) { leftIndex, rightIndex := 0, len(arr) - 1 return recursive(arr, leftIndex, rightIndex, target) } func recursive(arr []int, leftIndex, rightIndex, target int) int { if leftIndex > rightIndex { // 未找到的退出条件 return -1 } middleIndex := (leftIndex + rightIndex) / 2 if arr[middleIndex] == target { // 找到的退出条件 return middleIndex } else if arr[middleIndex] > target { //取左侧一半数组 return recursive(arr, leftIndex, middleIndex - 1, target) } else { //取右侧一半的数组 return recursive(arr, middleIndex + 1, rightIndex, target) } }
测试:
func main() { arr := []int{1,3,5,6,9,10,11,13,14,15} target := 7 fmt.Println(BinarySearch(arr, target)) }
解题思路
从题目中我们可以看出核心问题是寻找两个数组中第K个数,K为两个数组中间的一个(数组之和为奇数)或两个数(数组之后为偶数),即:
我们以下面一组case为例:
image.png
我们需要找到第7和第8个数,求平均。这里我们以第7个数为例进行说明。
首先我们先查找k/2=7/2=3个数据,比较两个数组的第三个元素的大小,我们发现5 < 8,于是我们删除第一个数组的前三个元素。
image.png
这里可能有人会问为什么删除第一个数组?因为我们需要保证删除的数据尽可能小,删除了5之后我们可以保证剩余数组中>=5的数的数量会大于整体长度的一半。在这个例子中大于等于5的元素的数量可以确定至少有(9+5)-3-2=9个,其中3是nums1中删除的元素数,2是nums中小于8的元素数。这样可以保证目标值不会被删除。
删除3个元素后,问题变成了寻找第k=7-3=4个元素。采用同样的方式:
image.png
我们删除4的一半个元素,即删除nums2中前2个元素。继续采用同样的方法删除剩余的2个元素中的一半:
image.png
当k=1时,我们只需要取两个数组第一个元素中较小的元素即可。
image.png
同时,我们需要注意两种边界问题:
- 当其中一个数组长度为0时,我们可以直接在另一个数组中获取目标值。
- 当其中一个数组长度小于k/2时,我们可以比较这个数组的最后一个元素。
源代码(Golang)
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { if (len(nums1) + len(nums2)) % 2 == 0 { return float64( findKth(nums1, nums2, (len(nums1) + len(nums2)) / 2) + findKth(nums1, nums2, (len(nums1) + len(nums2)) / 2 + 1)) / 2.0 } return float64(findKth(nums1, nums2, (len(nums1) + len(nums2)) / 2 + 1)) } func findKth(nums1, nums2 []int, k int) int { if len(nums1) == 0 { return nums2[k - 1] } if len(nums2) == 0 { return nums1[k - 1] } if k == 1 { return min(nums1[0], nums2[0]) } var num1 int var num2 int var to1 int var to2 int if k / 2 > len(nums1) { num1 = nums1[len(nums1) - 1] to1 = len(nums1) } else { num1 = nums1[k / 2 - 1] to1 = k / 2 } if k / 2 > len(nums2) { num2 = nums2[len(nums2) - 1] to2 = len(nums2) } else { num2 = nums2[k / 2 - 1] to2 = k / 2 } if num1 > num2 { return findKth(nums1, nums2[to2:], k - to2) } return findKth(nums1[to1:], nums2, k - to1) } func min(a, b int) int { if a < b { return a } return b }
有疑问加站长微信联系
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Concepts, Techniques, and Models of Computer Programming
Peter Van Roy、Seif Haridi / The MIT Press / 2004-2-20 / USD 78.00
This innovative text presents computer programming as a unified discipline in a way that is both practical and scientifically sound. The book focuses on techniques of lasting value and explains them p......一起来看看 《Concepts, Techniques, and Models of Computer Programming》 这本书的介绍吧!