Loading [MathJax]/jax/input/TeX/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >2022-04-27:Alice 有一个下标从 0 开始的数组 arr ,由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0

2022-04-27:Alice 有一个下标从 0 开始的数组 arr ,由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0

原创
作者头像
福大大架构师每日一题
发布于 2022-04-27 14:56:29
发布于 2022-04-27 14:56:29
8570
举报

2022-04-27:Alice 有一个下标从 0 开始的数组 arr ,由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher :

对每个满足 0 <= i < n 的下标 i ,loweri = arri - k

对每个满足 0 <= i < n 的下标 i ,higheri = arri + k

不幸地是,Alice 丢失了全部三个数组。但是,她记住了在数组 lower 和 higher 中出现的整数,但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。

给你一个由 2n 个整数组成的整数数组 nums ,其中 恰好 n 个整数出现在 lower ,剩下的出现在 higher ,还原并返回 原数组 arr 。如果出现答案不唯一的情况,返回 任一 有效数组。

注意:生成的测试用例保证存在 至少一个 有效数组 arr 。

输入:nums = 2,10,6,4,8,12

输出:3,7,11

解释:

如果 arr = 3,7,11 且 k = 1 ,那么 lower = 2,6,10 且 higher = 4,8,12 。

组合 lower 和 higher 得到 2,6,10,4,8,12 ,这是 nums 的一个排列。

另一个有效的数组是 arr = 5,7,9 且 k = 3 。在这种情况下,lower = 2,4,6 且 higher = 8,10,12 。

力扣2122. 还原原数组。

来自小米。

答案2022-04-27:

先排序。大数的第1个数需要循环。

时间复杂度:O(N**2)。

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

代码语言:rust
AI代码解释
复制
fn main() {
    let mut nums: Vec<isize> = vec![2, 10, 6, 4, 8, 12];
    let ans: Vec<isize> = recover_array(&mut nums);
    println!("ans = {:?}", ans);
}

fn recover_array(nums: &mut Vec<isize>) -> Vec<isize> {
    nums.sort_by(|a, b| a.cmp(&b));
    let n = nums.len() as isize;
    // nums[0] -> 小数组的第0个
    let m = n >> 1;
    // 谁是大数组的第0个?不知道,试!first位置的数!
    for first in 1..=m {
        // d = 2 * k; k正数!
        let d = nums[first as usize] - nums[0];
        if d > 0 && (d & 1) == 0 {
            // 试图生成原始数组!ans!
            let mut ans: Vec<isize> = vec![];
            for _k in 0..m {
                ans.push(0);
            }
            let mut i: isize = 0;
            let mut set: Vec<bool> = vec![];
            for _k in 0..n {
                set.push(false);
            }
            let k: isize = d >> 1;
            let mut l: isize = 0;
            let mut r: isize = first;
            while r < n {
                while set[l as usize] {
                    l += 1;
                }
                if l == r {
                    r += 1;
                } else if nums[r as usize] - nums[l as usize] > d {
                    break;
                } else if nums[r as usize] - nums[l as usize] < d {
                    r += 1;
                } else {
                    set[r as usize] = true;
                    r += 1;
                    ans[i as usize] = nums[l as usize] + k;
                    l += 1;
                    i += 1;
                }
            }
            if i == m {
                return ans;
            }
        }
    }
    return vec![];
}

执行结果如下:

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

左神java代码

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

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

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
2022-04-25:给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。 输入: nums
2022-04-25:给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
福大大架构师每日一题
2022/04/25
6500
排序+双指针题目类型
一个整数数组 original 可以转变成一个 双倍 数组 changed ,转变方式为将 original 中每个元素 值乘以 2 加入数组中,然后将所有元素 随机打乱 。
公众号guangcity
2022/01/18
3400
2022-04-13:给你一个下标从 0 开始包含 n 个正整数的数组 arr ,和一个正整数 k 。
2022-04-13:给你一个下标从 0 开始包含 n 个正整数的数组 arr ,和一个正整数 k 。
福大大架构师每日一题
2022/04/13
4500
2022-04-22:给你两个正整数数组 nums 和 target ,两个数组长度相等。 在一次操作中,你可以选择两个 不同 的下标 i 和 j , 其中 0
2022-04-22:给你两个正整数数组 nums 和 target ,两个数组长度相等。
福大大架构师每日一题
2023/04/22
1.4K0
2022-04-22:给你两个正整数数组 nums 和 target ,两个数组长度相等。 在一次操作中,你可以选择两个 不同 的下标 i 和 j , 其中 0
2022-07-13:给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。 每一步,你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j
2022-07-13:给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。
福大大架构师每日一题
2022/07/13
7630
2022-07-13:给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。 每一步,你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j
2023-03-18:给定一个长度n的数组,每次可以选择一个数x, 让这个数组中所有的x都变成x+1,问你最少的操作次数, 使得这个数组变成一个非降数组。 n
本题可以用多种算法来解决,下面我们将介绍四种常见的做法,分别是暴力枚举、动态规划、单调栈和差分。
福大大架构师每日一题
2023/03/18
1K0
2023-03-18:给定一个长度n的数组,每次可以选择一个数x, 让这个数组中所有的x都变成x+1,问你最少的操作次数, 使得这个数组变成一个非降数组。 n
2022-12-20:二狗买了一些小兵玩具,和大胖一起玩, 一共有n个小兵,这n个小兵拍成一列, 第i个小兵战斗力为hi,然后他们两个开始对小兵进行排列, 一共
2022-12-20:二狗买了一些小兵玩具,和大胖一起玩,一共有n个小兵,这n个小兵拍成一列,第i个小兵战斗力为hi,然后他们两个开始对小兵进行排列,一共进行m次操作,二狗每次操作选择一个数k,将前k个小兵战斗力从小到大排列,大胖每次操作选择一个数k,将前k个小兵战斗力从大到小排列,问所有操作结束后,排列顺序什么样,给定一个长度为n的数组arr,表示每个小兵的战斗力,给定一个长度为m的数组op, opi = { k , 0 }, 表示对前k个士兵执行从小到大的操作,opi = { k , 1 }, 表示对前
福大大架构师每日一题
2022/12/20
1910
2022-12-20:二狗买了一些小兵玩具,和大胖一起玩, 一共有n个小兵,这n个小兵拍成一列, 第i个小兵战斗力为hi,然后他们两个开始对小兵进行排列, 一共
2022-04-17:给定一个数组arr,其中的值有可能正、负、0, 给定一个正数k。 返回累加和>=k的所有子数组中,最短的子数组长度。 来自字节跳动。力扣8
2022-04-17:给定一个数组arr,其中的值有可能正、负、0, 给定一个正数k。 返回累加和>=k的所有子数组中,最短的子数组长度。 来自字节跳动。力扣862。 答案2022-04-17: 看到子数组,联想到结尾怎么样,开头怎么样。 预处理前缀和,单调栈。 达标的前缀和,哪一个离k最近? 单调栈+二分。复杂度是O(N*logN)。 双端队列。 时间复杂度:O(N)。 代码用rust编写。代码如下: fn main() { let arr: Vec<isize> = vec![2, -1, 2]
福大大架构师每日一题
2022/04/17
1.6K0
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线, 给定一个有序数组arr,表示现在哪些树已经没了,arr[i]一定在[1,n]
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线,
福大大架构师每日一题
2022/06/05
2140
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线, 给定一个有序数组arr,表示现在哪些树已经没了,arr[i]一定在[1,n]
2022-10-15:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。 你可以按 任意顺序 返回答案。
2022-10-15:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。
福大大架构师每日一题
2022/10/16
7100
2022-10-15:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。 你可以按 任意顺序 返回答案。
2022-04-22:给你两个正整数数组 nums 和 target ,两个数组长度相等。
2022-04-22:给你两个正整数数组 nums 和 target ,两个数组长度相等。 在一次操作中,你可以选择两个 不同 的下标 i 和 j , 其中 0 <= i, j < nums.length ,并且: 令 nums[i] = nums[i] + 2 且 令 nums[j] = nums[j] - 2 。 如果两个数组中每个元素出现的频率相等,我们称两个数组是 相似 的。 请你返回将 nums 变得与 target 相似的最少操作次数。 测试数据保证 nums 一定能变得与 target 相似。 输入:nums = [8,12,6], target = [2,14,10]。 输出:2。
福大大架构师每日一题
2023/06/09
1880
2022-04-22:给你两个正整数数组 nums 和 target ,两个数组长度相等。
2022-11-16:给你一个数组 nums,我们可以将它按一个非负整数 k 进行轮调, 例如,数组为 nums = [2,4,1,3,0], 我们按 k =
2022-11-16:给你一个数组 nums,我们可以将它按一个非负整数 k 进行轮调,
福大大架构师每日一题
2022/11/16
2550
2022-11-16:给你一个数组 nums,我们可以将它按一个非负整数 k 进行轮调, 例如,数组为 nums = [2,4,1,3,0], 我们按 k =
2022-04-13:给你一个下标从 0 开始包含 n 个正整数的数组 arr ,和一个正整数 k 。
2022-04-13:给你一个下标从 0 开始包含 n 个正整数的数组 arr ,和一个正整数 k 。
福大大架构师每日一题
2022/06/04
4800
2022-04-13:给你一个下标从 0 开始包含 n 个正整数的数组 arr ,和一个正整数 k 。
2022-09-07:给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如,序列 [4,6,16
数组的一个 子序列 本质是一个序列,可以通过删除数组中的某些元素(或者不删除)得到。
福大大架构师每日一题
2022/09/07
7450
2022-09-07:给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如,序列 [4,6,16
2023-06-02:给定一个二进制数组 nums 和一个整数 k, k位翻转 就是从 nums 中选择一个长度为 k 的 子数组, 同时把子数组中的每一个 0
1.初始化一个大小为 $n$ 的队列 queue,用于存储需要翻转的子数组的起始下标。
福大大架构师每日一题
2023/06/02
6380
2022-05-02:给定一个数组arr,一个正数num,一个正数k,可以把arr中的某些数字拿出来组成一组,要求该组中的最大值
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_02_3_week/Code04_MaxTeamNumber.java)
福大大架构师每日一题
2022/06/04
8100
2022-05-02:给定一个数组arr,一个正数num,一个正数k,可以把arr中的某些数字拿出来组成一组,要求该组中的最大值
2023-12-30:用go语言,给你一个下标从 0 开始的整数数组 nums ,它包含 n 个 互不相同 的正整数, 如果 n
2023-12-30:用go语言,给你一个下标从 0 开始的整数数组 nums ,它包含 n 个 互不相同 的正整数,
福大大架构师每日一题
2024/01/05
2100
2023-12-30:用go语言,给你一个下标从 0 开始的整数数组 nums ,它包含 n 个 互不相同 的正整数, 如果 n
2022-06-14:数组的最大与和。 给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ,满足2 * numSlots >= n 。总共
给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ,满足2 * numSlots >= n 。总共有 numSlots 个篮子,编号为 1 到 numSlots 。
福大大架构师每日一题
2022/06/14
5560
2022-06-14:数组的最大与和。 给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ,满足2 * numSlots >= n 。总共
2022-05-07:返回一个数组中,所有降序三元组的数量。
2022-05-07:返回一个数组中,所有降序三元组的数量。 比如 : {5, 3, 4, 2, 1}, 所有降序三元组为 : {5, 3, 2}、{5, 3, 1}、{5, 4, 2}、{5, 4, 1}、 {5, 2, 1}、{3, 2, 1}、{4, 2, 1}。 所以返回数量7。 答案2022-05-07: 利用index tree。 时间复杂度:O(N * logN)。 空间复杂度:O(N)。 代码用rust编写。代码如下: fn main() { let mut arr: Vec<is
福大大架构师每日一题
2022/05/07
7120
2022-11-18:给定一个数组arr,表示连续n天的股价,数组下标表示第几天指标X:任意两天的股价之和 - 此两天间隔的天数
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_4_week/Code01_MaxXFromStock.java)
福大大架构师每日一题
2023/02/01
2470
推荐阅读
2022-04-25:给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。 输入: nums
6500
排序+双指针题目类型
3400
2022-04-13:给你一个下标从 0 开始包含 n 个正整数的数组 arr ,和一个正整数 k 。
4500
2022-04-22:给你两个正整数数组 nums 和 target ,两个数组长度相等。 在一次操作中,你可以选择两个 不同 的下标 i 和 j , 其中 0
1.4K0
2022-07-13:给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。 每一步,你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j
7630
2023-03-18:给定一个长度n的数组,每次可以选择一个数x, 让这个数组中所有的x都变成x+1,问你最少的操作次数, 使得这个数组变成一个非降数组。 n
1K0
2022-12-20:二狗买了一些小兵玩具,和大胖一起玩, 一共有n个小兵,这n个小兵拍成一列, 第i个小兵战斗力为hi,然后他们两个开始对小兵进行排列, 一共
1910
2022-04-17:给定一个数组arr,其中的值有可能正、负、0, 给定一个正数k。 返回累加和>=k的所有子数组中,最短的子数组长度。 来自字节跳动。力扣8
1.6K0
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线, 给定一个有序数组arr,表示现在哪些树已经没了,arr[i]一定在[1,n]
2140
2022-10-15:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。 你可以按 任意顺序 返回答案。
7100
2022-04-22:给你两个正整数数组 nums 和 target ,两个数组长度相等。
1880
2022-11-16:给你一个数组 nums,我们可以将它按一个非负整数 k 进行轮调, 例如,数组为 nums = [2,4,1,3,0], 我们按 k =
2550
2022-04-13:给你一个下标从 0 开始包含 n 个正整数的数组 arr ,和一个正整数 k 。
4800
2022-09-07:给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如,序列 [4,6,16
7450
2023-06-02:给定一个二进制数组 nums 和一个整数 k, k位翻转 就是从 nums 中选择一个长度为 k 的 子数组, 同时把子数组中的每一个 0
6380
2022-05-02:给定一个数组arr,一个正数num,一个正数k,可以把arr中的某些数字拿出来组成一组,要求该组中的最大值
8100
2023-12-30:用go语言,给你一个下标从 0 开始的整数数组 nums ,它包含 n 个 互不相同 的正整数, 如果 n
2100
2022-06-14:数组的最大与和。 给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ,满足2 * numSlots >= n 。总共
5560
2022-05-07:返回一个数组中,所有降序三元组的数量。
7120
2022-11-18:给定一个数组arr,表示连续n天的股价,数组下标表示第几天指标X:任意两天的股价之和 - 此两天间隔的天数
2470
相关推荐
2022-04-25:给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。 输入: nums
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档