Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/932.html

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

  • class Solution {
    public int[] beautifulArray(int N) {
        int log = (int) Math.ceil(Math.log(N) / Math.log(2));
        int power2 = (int) Math.pow(2, log);
        int[] beautifulArrayPower2 = new int[power2];
        beautifulArrayPower2[0] = 1;
        for (int length = 1; length < power2; length *= 2) {
            for (int i = 0; i < length; i++)
                beautifulArrayPower2[i] *= 2;
            for (int i = 0; i < length; i++)
                beautifulArrayPower2[length * 2 - i - 1] = beautifulArrayPower2[i] - 1;
        }
        int[] beautifulArray = new int[N];
        int index = 0;
        for (int i = 0; i < power2; i++) {
            int num = beautifulArrayPower2[i];
            if (num <= N) {
                beautifulArray[index] = num;
                index++;
            }
        }
        return beautifulArray;
    }
}

############

class Solution {
    public int[] beautifulArray(int n) {
        if (n == 1) {
            return new int[] {1};
        }
        int[] left = beautifulArray((n + 1) >> 1);
        int[] right = beautifulArray(n >> 1);
        int[] ans = new int[n];
        int i = 0;
        for (int x : left) {
            ans[i++] = x * 2 - 1;
        }
        for (int x : right) {
            ans[i++] = x * 2;
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/beautiful-array/
// 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);
    }
};

  • class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        if n == 1:
            return [1]
        left = self.beautifulArray((n + 1) >> 1)
        right = self.beautifulArray(n >> 1)
        left = [x * 2 - 1 for x in left]
        right = [x * 2 for x in right]
        return left + right

############

class Solution(object):
    def beautifulArray(self, N):
        """
        :type N: int
        :rtype: List[int]
        """
        res = [1]
        while len(res) < N:
            res = [2 * i - 1 for i in res] + [2 * i  for i in res]
        return [i for i in res if i <= N]

  • func beautifulArray(n int) []int {
	if n == 1 {
		return []int{1}
	}
	left := beautifulArray((n + 1) >> 1)
	right := beautifulArray(n >> 1)
	var ans []int
	for _, x := range left {
		ans = append(ans, x*2-1)
	}
	for _, x := range right {
		ans = append(ans, x*2)
	}
	return ans
}

All Problems

All Solutions