golang刷leetcode技巧之如何实现排序变形
小编给大家分享一下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技巧之如何实现排序变形
URL标题：http://6mz.cn/article/jgdsoj.html