Sắp xếp đẹp II trong C ++

Giả sử chúng ta có hai số nguyên n và k, chúng ta cần tạo một danh sách chứa n số nguyên dương khác nhau, từ 1 đến n và tuân theo quy tắc sau -

Xét danh sách là [a1, a2, a3, ..., an] thì danh sách [| a1 - a2 |, | a2 - a3 |, | a3 - a4 |, ..., | an-1 - an |] có đúng k số nguyên duy nhất. Vì vậy, nếu có nhiều câu trả lời, hãy hiển thị bất kỳ câu trả lời nào trong số đó.

Nếu đầu vào là n =3 và k =2, thì kết quả sẽ là [1,3,2]. [1,3,2] có ba số nguyên dương khác nhau từ 1 đến 3. Và [2,1] có đúng 2 số nguyên phân biệt 1 và 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định ret mảng
• cho i:=1, j:=n, kiểm tra xem tôi có <=j
  • nếu k> 1, thì
    • nếu k là số lẻ thì chèn i, nếu không thì chèn j vào ret
    • nếu k lẻ thì tăng i lên 1, ngược lại giảm j đi 1
    • giảm k đi 1
  • nếu không thì chèn i vào res và tăng i lên 1
• trả lời lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

3
2

Đầu ra

[3, 1, 2, ]