难度: 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
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******
我还有什么话可以说呢，给寒神 跪了
还有视频讲解
另外感谢二哥给我指导
思路就是 全奇数beautiful array odds + [odd + 1 for odd in odds]
- Deletion
- Easy to prove.
- Addition
-
If we have A[k] * 2 != A[i] + A[j],
-
(A[k] + x) * 2 = A[k] * 2 + 2x != A[i] + A[j] + 2x = (A[i] + x) + (A[j] + x)
-
E.g: [1,3,2] + 1 = [2,4,3].
- Multiplication
-
If we have A[k] * 2 != A[i] + A[j],
-
(A[k] * x) * 2 = A[k] * 2 * x != (A[i] + A[j]) * x = (A[i] * x) + (A[j] * x)
-
E.g: [1,3,2] * 2 = [2,6,4]
With the observations above, we can easily construct any beautiful array. Assume we have a beautiful array A with length N
- A1 = A * 2 - 1 is beautiful with only odds from 1 to N * 2 -1
- A2 = A * 2 is beautiful with only even from 2 to N * 2
- B = A1 + A2 beautiful array with length N
E.g:
A = [2, 1, 4, 5, 3]
A1 = [3, 1, 7, 9, 5]
A2 = [4, 2, 8, 10, 6]
B = A1 + A2 = [3, 1, 7, 9, 5, 4, 2, 8, 10, 6]
我都不忍心改动，这代码真tm优美！！！
class Solution(object):
def beautifulArray(self, N):
"""
:type N: int
:rtype: List[int]
"""
res = [1]
while len(res) < N:
res = [i * 2 - 1 for i in res] + [i * 2 for i in res]
return [i for i in res if i <= N]思路 2 - 时间复杂度: O(NlgN)- 空间复杂度: O(1)******
class Solution(object):
def beautifulArray(self, N):
"""
:type N: int
:rtype: List[int]
"""
return sorted(range(1, N + 1), key=lambda x: bin(x)[:1:-1])思路 3 - 时间复杂度: O(NlgN)- 空间复杂度: O(1)******
递归
class Solution(object):
def beautifulArray(self, N):
"""
:type N: int
:rtype: List[int]
"""
return [i * 2 for i in self.beautifulArray(N / 2)] + [i * 2 - 1 for i in self.beautifulArray((N + 1) / 2)] if N > 1 else [1]