Description
An array nums of length n is beautiful if:
nums is a permutation of the integers in the range [1, n].- For every
0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].
Given the integer n, return any beautiful array nums of length n. There will be at least one valid answer for the given n.
Example 1:
Input: n = 4
Output: [2,1,4,3]
Example 2:
Input: n = 5
Output: [3,1,2,5,4]
Constraints:
Solutions
Solution 1
PythonJavaC++Go
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(code-box)
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;
}
}(code-box)
class Solution {
public:
vector<int> beautifulArray(int n) {
if (n == 1) return {1};
vector<int> left = beautifulArray((n + 1) >> 1);
vector<int> right = beautifulArray(n >> 1);
vector<int> ans(n);
int i = 0;
for (int& x : left) ans[i++] = x * 2 - 1;
for (int& x : right) ans[i++] = x * 2;
return ans;
}
};(code-box)
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
}(code-box)
