十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
小编给大家分享一下golang刷leetcode技巧之如何实现排序变形,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
创新互联主营溆浦网站建设的网络公司,主营网站建设方案,重庆APP开发,溆浦h5成都微信小程序搭建,溆浦网站营销推广欢迎溆浦等地区企业咨询
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
解题思路:
1,因为两部分仍然有序所以可以二分查找
2,如果arr[mid] 给定一个整数数组,编写一个函数,找出索引m和n,只要将索引区间[m,n]的元素排好序,整个数组就是有序的。注意:n-m尽量最小,也就是说,找出符合条件的最短序列。函数返回值为[m,n],若不存在这样的m和n(例如整个数组是有序的),请返回[-1,-1]。 示例: 输入:[1,2,4,7,10,11,7,12,6,7,16,18,19] 输出:[3,9] 提示: 0 <= len(array) <= 1000000 解题思路: 1,将数组划分成三部分,左边的最大值一定小于中间和右边部分 从左往右遍历,依次取最大值,最后一个比最大值小的位置,是中间部分的右边界(因为右边部分,比中间和左边大) 2,右边最小值比中间和左边部分大,从最右往左遍历,取最小值,最后一个比最小值大的位置就是左边界 3,看左边界是不是比右边界小 代码实现: 以上是“golang刷leetcode技巧之如何实现排序变形”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!func findMin(nums []int) int {
return find(nums,0,len(nums)-1)
}
func find(nums[]int ,l,r int)int{
mid:=(l+r)/2
if mid==l ||mid==r{
if nums[l]
return nums[l]
}
return nums[r]
}
if nums[mid]
return find(nums,l,mid)
}
return find(nums,mid,r)
}
部分排序
func subSort(array []int) []int {
le:=len(array)-1
if le<1{
return []int{-1,-1}
}
min:=1000000
max:=-1000000
l:=le
r:=0
/**
1,2,4, || 7,10,11,7,12,6,7, || 16,18,19
左边 中间 右边
最后是三个部分,左边的最大值必须小于其右边(中间和右边)的最小值,
右边的最小值必须大于其左边(左边和中间)的最大值;
那么从左往右找的是最大值,如果出现小于左边最大值的情况,那么更新 rightindex,最后的 rightindex 右边的必然大于这个最大值;
从右往左找的是最小值,如果出现大于这个值的情况,那么更新 leftindex,
最后的 leftindex 左边的必然小于这个最小值;
*/
for i:=0;i<=le;i++{
if array[i]>=max{
max=array[i]
}else{
r=i
}
if array[le-i]<=min{
min=array[le-i]
}else{
l=le-i
}
}
if l
return []int{l,r}
}
return []int{-1,-1}
}
文章标题:golang刷leetcode技巧之如何实现排序变形
本文地址:http://6mz.cn/article/jgdsoj.html