C++ 中的美丽排列 II

假设我们有两个整数 n 和 k，我们需要构造一个列表，该列表包含 n 个不同的正整数，范围从 1 到 n，并遵循以下规则：

假设列表为 [a1, a2, a3, ... , an]，则列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 恰好有 k 个唯一的整数。因此，如果有多个答案，则显示其中任何一个。

如果输入类似于 n = 3 和 k = 2，则结果将为 [1,3,2]。[1,3,2] 包含三个不同的正整数，范围从 1 到 3。并且 [2,1] 恰好有 2 个不同的整数 1 和 2。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个数组 ret
  • 对于 i := 1，j := n，检查 i <= j
    • 如果 k > 1，则
      • 如果 k 是奇数，则将 i 插入 ret，否则将 j 插入 ret
      • 如果 k 是奇数，则将 i 增加 1，否则将 j 减小 1
      • 将 k 减小 1
    • 否则将 i 插入 res 并将 i 增加 1
  • 返回 ret

让我们看看以下实现以更好地理解：

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> constructArray(int n, int k) {
      vector <int> ret;
      for(int i = 1, j = n; i <= j; ){
         if(k > 1){
            ret.push_back(k % 2 ? i : j);
            if(k % 2 == 1){
               i++;
            }else j--;
            k--;
         } else {
            ret.push_back(i++);
        }
      }
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.constructArray(3, 2));
}

输入

3
2

输出

[3, 1, 2, ]

更新于: 2020年5月4日

131 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告