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]

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)}
部分排序

给定一个整数数组,编写一个函数,找出索引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,看左边界是不是比右边界小

代码实现:

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技巧之如何实现排序变形”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!


本文名称:golang刷leetcode技巧之如何实现排序变形
分享路径:http://pwwzsj.com/article/jgdsoj.html