932. Beautiful Array

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

Approach #1: divide and conquer. [C++]

class Solution {

public:

    vector<int> beautifulArray(int N) {

        vector<int> ans;

        ans.push_back(1);

        while (ans.size() < N) {

            vector<int> temp;

            for (int i : ans) if (i * 2 - 1 <= N) temp.push_back(i*2-1);

            for (int i : ans) if (i * 2 <= N) temp.push_back(i*2);

            ans = temp;

        }

        return ans;

    }

};

Approach #2: [Python]

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]

Analysis:

https://leetcode.com/problems/beautiful-array/discuss/186679/C%2B%2BJavaPython-Odd-%2B-Even-Pattern-O(N)

巴特西

932. Beautiful Array

最新文章

热门文章