932

932. Beautiful Array (Medium)

For some fixed N, an array A is beautiful if it is a permutation of the integers 1, 2, ..., N, such that:

For every i < j, there is no k with i < k < j such that A[k] * 2 = A[i] + A[j].

Given N, return any beautiful array A.  (It is guaranteed that one exists.)

 

Example 1:

Input: 4
Output: [2,1,4,3]

Example 2:

Input: 5
Output: [3,1,2,5,4]

 

Note:

• 1 <= N <= 1000

 

Related Topics:
Divide and Conquer

Solution 1. Divide and Conquer

Observations:

• Given 2 * A[k] != A[i] + A[j], since 2 * A[k] is even, we can make A[i] an odd number and A[j] an even number. So we can split the array into two parts, all the odd numbers into left and all the even numbers into right.
• We can reuse the solution to 1 2 3 4 5 to construct the solution for 1 3 5 7 9.

// OJ: https://leetcode.com/problems/beautiful-array/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(NlogN)
class Solution {
    unordered_map<int, vector<int>> m;
    vector<int> dfs(int N) {
        if (m.count(N)) return m[N];
        vector<int> ans(N);
        if (N == 1) ans[0] = 1;
        else {
            int t = 0;
            for (int x : dfs((N + 1) / 2)) ans[t++] = 2 * x - 1; // odd
            for (int x : dfs(N / 2)) ans[t++] = 2 * x; // even
        }
        return m[N] = ans;
    }
public:
    vector<int> beautifulArray(int N) {
        return dfs(N);
    }
};