前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-11-16:给你一个数组 nums,我们可以将它按一个非负整数 k 进行轮调, 例如,数组为 nums = [2,4,1,3,0], 我们按 k =

2022-11-16:给你一个数组 nums,我们可以将它按一个非负整数 k 进行轮调, 例如,数组为 nums = [2,4,1,3,0], 我们按 k =

原创
作者头像
福大大架构师每日一题
发布2022-11-16 23:02:26
2100
发布2022-11-16 23:02:26
举报

2022-11-16:给你一个数组 nums,我们可以将它按一个非负整数 k 进行轮调,

例如,数组为 nums = 2,4,1,3,0,

我们按 k = 2 进行轮调后,它将变成 1,3,0,2,4。

这将记为 3 分,

因为 1 > 0 不计分、3 > 1 不计分、0 <= 2 计 1 分、

2 <= 3 计 1 分,4 <= 4 计 1 分。

在所有可能的轮调中,返回我们所能得到的最高分数对应的轮调下标 k 。

如果有多个答案,返回满足条件的最小的下标 k 。

输入:nums = 2,3,1,4,0。

输出:3。

答案2022-11-16:

力扣798。差分数组。

时间复杂度:O(N)。

空间复杂度:O(N)。

代码用rust编写。代码如下:

代码语言:rust
复制
use std::iter::repeat;

impl Solution {
    pub fn best_rotation(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        // cnt : 差分数组
        // cnt最后进行前缀和的加工!
        // 加工完了的cnt[0] :  整体向右移动0的距离, 一共能得多少分
        // 加工完了的cnt[i] :  整体向右移动i的距离, 一共能得多少分
        let mut cnt: Vec<i32> = repeat(0).take((n + 1) as usize).collect();
        for i in 0..n {
            // 遍历每个数!
            // 看看每个数,对差分数组哪些范围,会产生影响!
            if nums[i as usize] < n {
                if i <= nums[i as usize] {
                    Solution::add(&mut cnt, nums[i as usize] - i, n - i - 1);
                } else {
                    Solution::add(&mut cnt, 0, n - i - 1);
                    Solution::add(&mut cnt, n - i + nums[i as usize], n - 1);
                }
            }
        }
        for i in 1..=n {
            cnt[i as usize] += cnt[(i - 1) as usize];
        }
        // 最大得分是啥!已经求出来了
        let mut max = cnt[0];
        let mut ans = 0;
        let mut i = n - 1;
        while i >= 1 {
            // 整体移动的i 0 n-1 n-2 n-3 1
            //         k 0  1   2   3   n-1
            if cnt[i as usize] > max {
                max = cnt[i as usize];
                ans = i;
            }
            i -= 1;
        }
        return if ans == 0 { 0 } else { n - ans };
    }
    fn add(cnt: &mut Vec<i32>, l: i32, r: i32) {
        cnt[l as usize] += 1;
        cnt[(r + 1) as usize] -= 1;
    }
}

fn main() {
    let nums = vec![2, 3, 1, 4, 0];
    let ans = Solution::best_rotation(nums);
    println!("ans = {:?}", ans);
}

struct Solution {}

执行结果如下:

在这里插入图片描述
在这里插入图片描述

左神java代码

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档