Skip to content

932. Beautiful Array 👎

  • Time: $O(n\log n)$
  • Space: $O(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
class Solution {
 public:
  vector<int> beautifulArray(int n) {
    vector<int> A(n);
    iota(A.begin(), A.end(), 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;
  }
};

 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
28
29
30
31
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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