快上网专注成都网站设计 成都网站制作 成都网站建设
成都网站建设公司服务热线:028-86922220

网站建设知识

十年网站开发经验 + 多家企业客户 + 靠谱的建站团队

量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决

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://6mz.cn/article/jgdsoj.html

免费获取网站建设与品牌策划方案报价

*主要业务范围包括:高端网站建设, 集团网站建设(网站建设网站制作)找网站建设公司就上快上网。
提交需求

    联系我们

    028-86922220
  • 手机:13518219792
  • 地址:成都市太升南路288号锦天国际A幢1002号
  • 24小时服务热线:400-028-6601

    网站建设服务

  • 网页设计
  • 网站制作
  • 网站开发

    网站推广服务

  • 营销网站建设
  • 百度快速排名
  • 整站网站推广

    网站运维服务

  • 基础维护
  • 网站改版
  • 网站维护

    FOLLOW US

  • 微信二维码

    微信二维码

Copyright © 2022 成都快上网科技有限公司 成都网站建设公司-选网站建设公司快上网!国内专业的网站制作公司!
All Rights Reserved 版权所有 蜀ICP备19037934号-11