Leetcode双周赛T4 将数组清空

月梦@剑心

发布于 2023-08-31 10:58:42

1000

发布于 2023-08-31 10:58:42

文章被收录于专栏：月梦·剑心的技术专栏月梦·剑心的技术专栏

将数组清空

给你一个包含若干互不相同整数的数组 nums ，你需要执行以下操作直到数组为空：

如果数组中第一个元素是当前数组中的最小值，则删除它。
否则，将第一个元素移动到数组的末尾。

请你返回需要多少个操作使 nums 为空。

代码

麻了，两份代码都是差九个用例，提示超时。

func countOperationsToEmptyArray(nums []int) int64 {
    var result int64 = 0
    for len(nums) != 0 {
        var i int64 = 0
        i = findMin(nums)
        result = result + i +1
        nums = append(nums[i+1:],nums[:i]...)
    }
    return result
}

func findMin(nums []int) int64 {
    min := 1000000000
    var index int64 = -1
    for k,v := range(nums){
        if v < min{
            min = v
            index = int64(k)
        }
    }
    return index
}

func countOperationsToEmptyArray(nums []int) int64 {
    var result int64 = 0
    var leng int64 = 0
    for _,v := range nums {
        v = v
        leng++
    }
    temp := make([]int,len(nums))
    copy(temp,nums)
    sort.Ints(temp)
    sign := 0
    for len(nums) != 0 {
        var i int64 = 0
        for i<leng {
            if nums[i] == temp[sign]{
                sign++
                break
            }
            i++
        }
        result = result + i +1
        nums = append(nums[i+1:],nums[:i]...)
    }
    return result
}

感觉有必要深入研究一下如何降低时间复杂度或者如何面对这种卡时间的题，周赛中经常遇到差几个用例然后一直超时的。明天再看看…

更新：看了讨论区的讨论，原来是要用线段树和树状数组做，数据结构选错了，但是现阶段我还用不上，先放放，之后再学这些。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-04-29，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构