Mảng đẹp trong C ++

Giả sử với một giá trị cố định nào đó của N, mảng A đẹp khi nó là hoán vị của các số nguyên 1, 2, ..., N, sao cho -

• Với mọi i

Giả sử chúng ta có N, chúng ta phải tìm một mảng A đẹp nào.

Vì vậy, nếu đầu vào là 5, thì đầu ra sẽ là [3,1,2,5,4]

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

• Tạo một mảng được gọi là ret, chèn 1 vào ret

• trong khi kích thước của ret

  • tạo tạm thời mảng

  • cho tôi trong phạm vi từ 0 đến kích thước của ret - 1

    • nếu ret [i] * 2 - 1 <=N, thì chèn ret [i] * 2 - 1 vào mảng tạm thời

  • cho tôi trong phạm vi từ 0 đến kích thước của ret - 1

  • nếu ret [i] * 2 <=N, thì chèn ret [i] * 2 vào mảng tạm thời

  • đặt ret:=temp

• trả lại ret

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<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> beautifulArray(int N) {
      vector <int> ret;
      ret.push_back(1);
      while(ret.size() < N){
         vector <int> temp;
         for(int i = 0; i < ret.size(); i++){
            if(ret[i] * 2 - 1 <= N) temp.push_back(ret[i] * 2 - 1);
         }
         for(int i = 0; i < ret.size(); i++){
            if(ret[i] * 2 <= N)temp.push_back(ret[i] * 2 );
         }
         ret = temp;
      }
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.beautifulArray(6));
}

Đầu vào

5

Đầu ra

[1,5,3,2,4]