Keshawn_lu's Blog

Leetcode 667. 优美的排列 II

字数统计: 490阅读时长: 2 min
2022/09/08 Share

题目简介：

给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：

  • 假设该列表是 answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。

返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。

示例 1：

1
2
3
输入：n = 3, k = 1
输出：[1, 2, 3]
解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1

提示：

  • 1 <= k < n <= 10^4

思路：

有点脑筋急转弯的感觉

当k = 1时，我们只需要像[1, 2, 3 , ...., n]这样排列即可

当k = n - 1时，我们需要将其按[1, n, 2, n - 1, 3, ....]，这样就会出现n - 1个不同的差值

所以，当我们需要k个不同差值的时候，我们只需要在数组的前半部分按照k = 1的情况进行排列，在后半部分按照k - n - 1的情况进行排列即可，最后数组就会变成[1, 2, ..., n - k - 1, n - k, n, n - k + 1, n - 1, ....]。

即前半部分为1个不同差值，后半部分为k个不同差值（一共为k + 1个元素）(其中一个差值与前半部分相同)，所以最后为k个不同差值。

tip:

  • 注意当n - k + ?和n - ?相等时，只需要压入一次元素即可（此时也是遍历的末尾）。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> constructArray(int n, int k) {

        vector<int> res;

        for(int i = 0; i < n - k - 1; i++)
            res.push_back(i + 1);	//前半段


        int i = n - k;
        int j = n;
        while(i < j){	//后半段

            res.push_back(i);
            res.push_back(j);

            i++;
            j--;
        }

        if(res.size() < n)	//i=j的情况，只需要压入一次
            res.push_back(i);

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网