LeetCode Solutions
class Solution {
public:
vector<int> beautifulArray(int n) {
vector<int> A(n);
iota(begin(A), end(A), 1);
divide(A, 0, n - 1, 1);
return A;
}
private:
void divide(vector<int>& A, int l, int r, int mask) {
if (l >= r)
return;
const int m = partition(A, l, r, mask);
divide(A, l, m, mask << 1);
divide(A, m + 1, r, mask << 1);
}
int partition(vector<int>& A, int l, int r, int mask) {
int nextSwapped = l;
for (int i = l; i <= r; ++i)
if (A[i] & mask)
swap(A[i], A[nextSwapped++]);
return nextSwapped - 1;
}
};
|
class Solution {
public int[] beautifulArray(int n) {
int[] A = new int[n];
for (int i = 0; i < n; ++i)
A[i] = i + 1;
divide(A, 0, n - 1, 1);
return A;
}
private void divide(int[] A, int l, int r, int mask) {
if (l >= r)
return;
final int m = partition(A, l, r, mask);
divide(A, l, m, mask << 1);
divide(A, m + 1, r, mask << 1);
}
private int partition(int[] A, int l, int r, int mask) {
int nextSwapped = l;
for (int i = l; i <= r; ++i)
if ((A[i] & mask) > 0)
swap(A, i, nextSwapped++);
return nextSwapped - 1;
}
private void swap(int[] A, int i, int j) {
final int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
|
class Solution:
def beautifulArray(self, n: int) -> List[int]:
A = [i for i in range(1, n + 1)]
def partition(l: int, r: int, mask: int) -> int:
nextSwapped = l
for i in range(l, r + 1):
if A[i] & mask:
A[i], A[nextSwapped] = A[nextSwapped], A[i]
nextSwapped += 1
return nextSwapped - 1
def divide(l: int, r: int, mask: int) -> None:
if l >= r:
return
m = partition(l, r, mask)
divide(l, m, mask << 1)
divide(m + 1, r, mask << 1)
divide(0, n - 1, 1)
return A
|
