天水+网站建设,北京最新消息今天,企业上云解决方案,渠道推广平台❓667. 优美的排列 II
难度#xff1a;中等
给你两个整数 n 和 k #xff0c;请你构造一个答案列表 answer #xff0c;该列表应当包含从 1 到 n 的 n 个不同正整数#xff0c;并同时满足下述条件#xff1a;
假设该列表是 answer [a1, a2, a3, ... , an] #xff0…❓667. 优美的排列 II
难度中等
给你两个整数 n 和 k 请你构造一个答案列表 answer 该列表应当包含从 1 到 n 的 n 个不同正整数并同时满足下述条件
假设该列表是 answer [a1, a2, a3, ... , an] 那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。
返回列表 answer 。如果存在多种答案只需返回其中 任意一种 。
示例 1 输入n 3, k 1 输出[1, 2, 3] 解释[1, 2, 3] 包含 3 个范围在 1-3 的不同整数并且 [1, 1] 中有且仅有 1 个不同整数1 示例 2 输入n 3, k 2 输出[1, 3, 2] 解释[1, 3, 2] 包含 3 个范围在 1-3 的不同整数并且 [2, 1] 中有且仅有 2 个不同整数1 和 2 提示 1 k n 1 0 4 1 k n 10^4 1kn104
思路
当 k1 时我们将 1∼n 按照 [1,2,⋯ ,n]的顺序进行排列那么相邻的差均为 1满足 k1 的要求。
当 kn−1 时我们将 1∼n 按照 [1, n, 2, n−1, 3, ⋯ ]的顺序进行交叉排列那么相邻的差从 n−1 开始依次递减 1。这样一来所有从 1 到 n−1的差值均出现一次满足 k n−1的要求。
所以对于其它的一般情况我们可以将这两种特殊情况进行合并即列表的前半部分相邻差均为 1后半部分相邻差从 k 开始逐渐递减到 1这样从 1 到 k 的差值均出现一次对应的列表即为 [ 1 , 2 , ⋯ , n − k , n , n − k 1 , n − 1 , n − k 2 , ⋯ ] [1,2,⋯,n−k,n,n−k1,n−1,n−k2,⋯] [1,2,⋯,n−k,n,n−k1,n−1,n−k2,⋯]
代码(Java、C)
Java
class Solution {public int[] constructArray(int n, int k) {int[] ans new int[n];for(int i 1; i n - k; i){//前半部分相邻差均为1ans[i - 1] i;}int low n - k 1;int high n;int i n - k;while(low high){//后半部分交叉排序ans[i] high--;if(i n) break;ans[i] low;}return ans;}
}C
class Solution {
public:vectorint constructArray(int n, int k) {vectorint ans(n);for(int i 1; i n - k; i){//前半部分相邻差均为1ans[i - 1] i;}int low n - k 1;int high n;int i n - k;while(low high){//后半部分交叉排序ans[i] high--;if(i n) break;ans[i] low;}return ans;}
};运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)这里不计入返回值需要的空间只需常数级空间。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我 leetCode专栏每日更新 注 如有不足欢迎指正
