题目

leetcode:1005

代码与解析


原文链接:K次取反后最大化的数组和

一开始,我做的方法是每次都将数组排序,然后取最小值,取负值

时间复杂度太高

// 不推荐
func largestSumAfterKNegations(nums []int, k int) int {
    for i:=0;i<k;i++{
        sort.Ints(nums)
        nums[0] = -nums[0]
    }
    sum := 0
    for _, v := range nums{
        sum += v
    }
    return sum
}

然后看了题解,
第一。三步很巧

第一步保证了,数组在有负值,负值变正后的顺序
第三部减少了遍历次数,

func largestSumAfterKNegations(nums []int, k int) int{
    // 第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
    sort.Slice(nums, func(i, j int)bool{
        return math.Abs(float64(nums[i]))>math.Abs(float64(nums[j]))
    })
    // 第二步:从前向后遍历,遇到负数将其变为正数,同时K--
    for i, _:= range nums{
        if nums[i]<0&&k>0{
            nums[i] = -nums[i]
            k--
        }
    }
    // 第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完
    // 这里有的大佬写的,if K%2 == 1 ,取余,如果余数奇数,那么就要变换一次
    for i:=0;i<k;i++{
        nums[len(nums)-1] = -nums[len(nums)-1]
    }
    // 求和
    res := 0
    for _,v := range nums{
        res += v
    }
    return res
}
if K%2 == 1 {
    nums[len(nums)-1] = -nums[len(nums)-1]
}

有大佬这样写,这样取余,看还需要变换符号次数

分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:191 个
  • 运行天数:1006 天
  • 访问总数:124185 人次

浙公网安备33011302000604

辽ICP备20003309号