[Lintcode] 932. Beautiful Array

本文主要是介绍[Lintcode] 932. Beautiful Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

# [Leetcode:932. Beautiful Array](https://leetcode.com/problems/beautiful-array/) 

- 本题难度: Hard
- Topic: divide-and-conquer
# Description

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

# 我的代码 
```python

import copy
import collections
class Solution:
    def beautifulArray(self,N):
        memo = {1: [1]}
        def f(N):
            if N not in memo:
                odds = f((N+1)//2)
                evens = f(N//2)
                memo[N] = [2*x-1 for x in odds] + [2*x for x in evens]
            return memo[N]
        return f(N)

```

# 超时的代码 

```python

noUse = {i+1 for i in range(N)}
use = collections.OrderedDict()
stack = [[use,noUse]]
while(len(stack)>0):[used_dic, nouse_set] = stack.pop()if len(nouse_set) == 0:return [item for item in used_dic]for toUse in nouse_set:f = 0for used in used_dic:tmp = used_dic.get((used+toUse)//2,-1)if tmp>used_dic[used]:f = 1breakif toUse*2-used in nouse_set:f = 1breakif f == 1:continuetmp_set = copy.copy(nouse_set)tmp_set.remove(toUse)tmp_dic = copy.copy(used_dic)tmp_dic[toUse] = len(used_dic)-1stack.append([tmp_dic,tmp_set])

```

思路

分治的思想，对左右半边来说，第一个数只取左边，第二个数只取右边，如果左右两边，一边奇数，一边偶数，则其平均数不会出现。
 

这篇关于[Lintcode] 932. Beautiful Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---