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]
, since2 * A[k]
is even, we can makeA[i]
an odd number andA[j]
an even number. So we can split the array into two parts, all theodd
numbers intoleft
and all the evennumbers
intoright
. - We can reuse the solution to
1 2 3 4 5
to construct the solution for1 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 }