题目描述
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
题意:给一个正整数N
,返回一个1-N
的全排列数组,并且这个数组有一个这样的性质,对于任意的i < j
,都不存在一个i < k < j
使得A[k] * 2 = A[i] + A[j]
。
算法1
(分治) $O(nlogn)$
题解1:分治,观察上述条件,如果A[i] + A[j]
是奇数的话,那么它们之间不管放什么数字都是无所谓的。所以我们首先考虑将数组划分为奇数和偶数两个部分1,3,5,7,…
和2,4,6,8,...
。这样我们将奇数部分放在数组的前半部分,偶数部分放在数组的后半部分。接下来,我们只需要关心奇数部分内部和偶数部分内部就可以了。考虑奇数部分1,3,5,7,...
,我们依然可以按照它们的坐标奇偶性分成1,5,9,13,…
和3,7,11,15,…
这样我们又只需要关心1,5,9,13,...
内部就可以了。所以这是一个不断分治的思想:不断的将当前数组的奇数坐标放在前面,偶数坐标放在后面。
C++ 代码
class Solution {
public:
vector<int> temp;
void solve(vector<int>& res,int l, int r)
{
if(l == r || l + 1 == r)
return;
int u = l,len = r - l + 1,mid = (l + r) >> 1;
for(int i = l ; i <= r ; i += 2)
temp[u ++] = res[i];
for(int i = l + 1 ; i <= r ; i += 2)
temp[u ++] = res[i];
for(int i = l ; i <= r ; i ++)
res[i] = temp[i];
solve(res,l,mid);
solve(res,mid + 1,r);
}
vector<int> beautifulArray(int N) {
vector<int> res(N);
temp = vector<int>(N);
for(int i = 0 ; i < N ; i ++)
res[i] = i + 1;
solve(res,0,N - 1);
return res;
}
};
算法2
(二进制反转表示) $O(nlogn)$
题解2:这一种解法就比较神奇了,对于一个数字N
,我们可以得到其二进制表示,然后我们将其二进制表示(reversed binary representation)反转过来记做RBR(N)
,因为这里N < 1000
,所以我们只需要取前10位就可以了。比如
1的二进制表示为00000 00001
,RBR(1) = 10000 00000
5的二进制表示为00000 00101
,RBR(5) = 10100 00000
接下来我们希望证明一个事情,对于任意的i < k < j
,如果i + j = 2 * k
,那么RBR(i) < RBR(k) < RBR(j)
永远不成立。如果上述猜想成立的话,我们只需要将所有的数字按照RBR(x)
的值从小到大排列就可以得到答案了。证明如下:
i,j
是偶数(二进制末尾为0),k
是奇数(二进制末尾为1)。那么RBR(i),RBR(j)
的首位为0,而RBR(K)
首位为1。有RBR(K) > RBR(i),RBR(k) > RBR(j)
。如2 + 4 = 2 * 3
i,j
是奇数(二进制末尾为1),k
是偶数(二进制末尾为1)。那么RBR(i),RBR(j)
的首位为1,而RBR(K)
首位为0。有RBR(K) < RBR(i),RBR(k) < RBR(j)
。如3 + 5 = 2 * 4
i,j,k
都是奇数,那么它们的RBR(i/j/k)
首位都是1,接下来我们需要比较第二位。我们令i1 = (i - 1) / 2
,j1 = (j - 1) / 2
,k1 = (k - 1) / 2
。这时候我们其实需要比较的是RBR(i1),RBR(j1),RBR(k1)
的大小。如1 + 9 = 2 * 5
i,j,k
都是偶数,那么它们的RBR(i/j/k)
首位都是0,接下来我们需要比较第二位。我们令i1 = i / 2
,j1 = j / 2
,k1 = k / 2
。这时候我们其实需要比较的是RBR(i1),RBR(j1),RBR(k1)
的大小。如1 + 7 = 2 * 4
对于情况3和情况4,他们在不断的除以2之后,总会划归为情况1和情况2的。
class Solution {
public:
int getRBR(int N)
{
int res = 0;
for(int i = 0 ; i <= 9 ; i ++)
res += (((N >> i) & 1) << (9 - i));
return res;
}
vector<int> beautifulArray(int N)
{
vector<int> res(N);
for(int i = 0 ; i < N ; i ++)
res[i] = i + 1;
sort(res.begin(),res.end(),[&](int i,int j){
return getRBR(i) < getRBR(j);
});
return res;
}
};