Beautiful Array
Similar Problems:
- LeetCode: 132 Pattern
- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #array, #dynamicprogramming, #divideconquer, #constructarray
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
Github: code.dennyzhang.com
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
- Solution:
// https://code.dennyzhang.com/beautiful-array
// Basic Ideas: array + dynamicprogramming
// [2, 1, 3]
// 2*i-1: [3, 1, 5]
// 2*i: [4, 2, 6]
// Put [odd...] [even...]
// Complexity: Time O(n), Space O(n)
func beautifulArray(N int) []int {
l := []int{1}
for len(l) < N {
l1, l2 := make([]int, len(l)), make([]int, len(l))
for i, v := range l {
l1[i], l2[i] = 2*v-1, 2*v
}
l = append(l1, l2...)
}
res := []int{}
for _, v := range l {
if v<=N {
res = append(res, v)
}
}
return res
}
