標籤：

一道阿里筆試題，思路應該是怎樣？

01-15

給定一個已經降序排好序的正數數組，要求按「最小、最大、次小、次大……」的順序重新排序。期望的時間複雜度為O(n)，空間複雜度為O(1)，即不能申請額外的數組。

例如：輸入[7,6,5,4,3,2,1]，輸出[1,7,2,6,3,5,4]。

最好講講思路是怎樣的，糾結了很久這題。

@賴威：請題主說明一下，原題是否說明數組內容為正整數且用有符號類型存儲，即提供了「符號位」這個每個元素 1 bit 的額外空間。

謝謝各位的作答，原題中是有說明必須是正數的

完美洗牌問題。

恰好昨天和學長 @熊風 討論了這個問題，我來說下我的做法。

首先，我們可以知道，如果排序後某個數的位置是i,那麼我可以O(1)時間得到該數在原數列中的位置。

那麼如果按照新位置-&>原位置-&>新位置-&>原位置的順序串起來，我們可以得到若干個環。

對於每個環，我們只需要一個變數，保護一下環上的某個點，然後順次做就好了。

另一個問題是我在從左往右掃的時候，由於空間複雜度的限制，無法知道某個點是否處於之前的環中。

我的做法是，由於題目中說所有數都是正數，因此我在每次賦值的時候，賦值成對應數的相反數就好了。

這樣每次掃到一個數，如果是負數，就說明被處理過了，不作處理。

處理完所有的數以後，再掃一遍變回正數就好了。

時間複雜度O(n),空間複雜度O(1)

論文中給的方法可以對任意數組進行交錯，但既然題中給了數組已排序這一信息，那就是允許而且鼓勵你利用這條信息的.
==========
第一種情況，數組元素均為非負數，可以用 @111qqz 的方法解決. (注意這個方法不需要元素的相對大小信息). 要注意的是標記要用取反操作. 在交換的過程中發現小於0的是已經被交換過的.
(注: 補碼錶示下，取反操作將0到INT_MAX一對一映射為-1到INT_MIN)

解釋一下這個思路的原理：對於任何一個元素，我們都可以只根據它原來的位置計算出新的位置(下面代碼中的getIndex函數)，而不需要知道這個元素具體是多大. 我們從第一個元素開始，通過getIndex計算它的位置，然後把它移到新位置上，這個元素的位置就固定了，用取反來標記. 原來新位置上原來元素就被「擠」走了，擠到的新位置，同樣也用getIndex取的新位置和用取反來標記. 重複這個過程直到所有元素都被移動到了自己的新位置.

第二種情況，數組元素有負數，我們可以將負數映射為非負數，然後用第一種情況的方法處理.
首先要記錄負數的個數，然後將所有負數取反(不會溢出).
這樣數組的元素都是非負的了. 由於原數組是排序過的，有多少負數我們是知道的，重新排列後我們可以將這些數再進行取反恢復成負數.

題目的特殊性在於，第一種情況並沒有利用元素的大小信息. 但是在第二種情況中，我們利用了原數列是排序過的這一信息，可以知道負數有多少個，以及其重新排序後的位置.

如果題目中的數組本身是無規律且正負數都沒有，就得用 @Eddium 給的方法了.

stackexchange上也有對數組無規律情況的討論 In-place algorithm for interleaving an array，高票回答給的論文就是@Eddium 給的論文.

更新：對於無符號數組情況的處理
我上面說的將負數映射為非負數是一種思想. 對於無符號數我們可以做類似的處理.
以8位無符號數為例，範圍為0 － 255， 共256個數，我們可以將其分成[0-127] 和 [128-255]兩個部分.
然後就和有符號數類似了，當數組元素均不小於128，也就是在[128-255]之間，我們可以把已經確定位置的數n標記為n-128，相當於把[128-255]映射到[0-127]，其它的同第一種情況.

當數組元素有小於128的，我們可以把小於128的元素數量記下來，並把所有小於128的元素全部加上128，然後類比我對有符號數的第二種情況作處理，最後再將其恢復回來.

貼個我當年助教的專欄吧：

完美洗牌問題線性演算法的兩篇論文 - 閱微堂 - 知乎專欄

原地完美洗牌論文

http://arxiv.org/pdf/0805.1598.pdf

中文解釋與實現

The-Art-Of-Programming-By-July/02.09.md at master · julycoding/The-Art-Of-Programming-By-July · GitHub

考慮索引排序，即當數組滿足題設的條件下，變換後的數組的索引固定。

引入rightCount變數用來記錄最右側排序的位置。

rightCount只向數組左側移動，移動距離為N/3。(N為數組長度)

數組的交換次數為N。

演算法的時間複雜度仍然為O(n)滿足題意。空間複雜度只用到了有限個變數，顯而易見是滿足的。

private static void ReCardsSortInPlace(int[] array)
{
if (array == null) throw new ArgumentNullException();
if (array.Length &< 2) return; if (array.Length == 2) { int temp = array[0]; array[0] = array[1]; array[1] = temp; return; } //因為循環不變式的初始條件是N&>=3所以，當N&<=2時只能靠手調了。 int swapTemp, swapTemp1, length = array.Length - 1, right = length; int k = right; int rightCount = right - 1; //循環進入條件，N&>=3，結束條件，從數組右側開始，當調整的位置的數量大於N/3時
while ((2 * (length - right + 1)) &<= right) { //循環初始條件 k = right; swapTemp1 = array[right]; do { k = ReIndex(k, length); swapTemp = array[k]; array[k] = swapTemp1; swapTemp1 = swapTemp; } while (right != k); //由於數組是遞減的，所以調整過的數組一定會滿足以下條件 while (array[rightCount] &> array[ReIndex(rightCount, length)])
{
rightCount--;
}
right = rightCount;//將未調整的循環的初始值重新賦予right變數
rightCount = right - 1;
}
}
private static int ReIndex(int index, int length)
{
if (index &<= length / 2) return (2 * index + 1 &> length) ? 2 * index : (2 * index + 1);
else
return (2 * (length - index));
}

測試代碼：

private static int[] ReCardsSort(int[] array)
{
int[] temp = new int[array.Length];
for (int i = 0; i &< array.Length; i++) { temp[ReIndex(i, array.Length - 1)] = array[i]; } return temp; } static int[] GetArray(int size) { var result = new int[size]; for (int i = 0; i &< size; i++) { result[size - 1 - i] = i; } return resu< } static void PrintArray(int[] array) { for (int i = 0; i &< array.Length; i++) { Console.Write(array[i] + " "); } Console.WriteLine(); } static void Main(string[] args) { bool flag = false; int right = 0, wrong = 0; for (int i = 3; i &< 10000; i++) { flag = false; int size = i; int[] array = GetArray(size); var result = ReCardsSort(array); ReCardsSortInPlace(array); for (int j = 0; j &< size; j++) { if (array[j] != result[j]) { flag = true; PrintArray(array); PrintArray(result); break; } } if (flag) { wrong++; } else { right++; } } Console.WriteLine("right:{0} wrong:{1}", right, wrong); }

測試結果：

之前想簡單了。不過最終解法還是很簡單：這個交換的思路可以用置換的方向來思考。最終代碼應當是不超過10行。

第一步自然是先考慮下標的通項，這個不難：當下標i為奇數時應是原數列的第i/2項，偶數時應為原數列的第n-1-i/2項。

然後就是考慮交換了：什麼樣的交換順序不會有額外影響？如果依照置換的方法來做，由於某些長度時整個交換過程包含多個群，就需要標記某個節點是否訪問過，會需要一些額外的內存而不符合要求。

那麼就要構造一下交換順序了……

臨時被叫去加班了，回來之後補上代碼和後續解析。

______________________________________________________

首先來說什麼叫置換

比方說，原有的下標

0 1 2 3 4 5

兌換完成後為

5 0 4 1 3 2

放一起看，可以得到交換順序

012345
504132
-------
052431

依照0-5-2-4-3-1的順序交換，可以得到最終排列。這個例子中恰好是1個群。

但是這個方法有一個小小的問題，即是

0123456
6051423
-------
0631 25 4

會形成3個群，也就是先要依次交換0-6-3-1然後交換2-5

這就會出現一個問題：當你交換完一個群之後，必須知道還剩下哪些群是沒有被交換的。倘若題目要求的是「正整數」，那完全可以用負號來標記，就可以寫成這樣。

def zigzag(a):
n = len(a)
count = 0 #運算時間
for i in xrange(n):
if a[i]&>0:
p=i
q=i/2 if i%2 else n-1-i/2
while q!=i:
count += 1
a[p], a[q] = -a[q], a[p]
if q%2:
p, q=q, q/2
else:
p, q=q, n-1-q/2
a[p] = -a[p]
for i in xrange(n):
a[i] = -a[i]
print count #循環次數
return a

for i in xrange(1, 10):
print zigzag(range(i, 0, -1))

這個東西的時間複雜度妥妥是O(n)可以不用糾結了。

這樣的計算是可行的，但是添加了附加條件：要麼必須是正整數，要麼就要開一片空間來計算，而這片空間是O(n)的，不符合題意。

那有沒有辦法不進行標記但是能夠起到效果呢？…弱雞的我表示想不出來了

感覺可以用索引排序？

首先，計算每個元素要挪到哪裡感覺很簡單，目測是這樣：

1. 舊位置i &< 2/n：新位置j＝2 * i +1

2. 舊位置i &>= 2/n: 新位置j = 2 * (n - 1 - i)

然後就是沿鏈輪換了。本例中 a[0]＝7應該被移到a[1], a[1]本來的數6應該被移到a[3], a[3]本來的數4應該被移到a[6]... 最後發現，把input數組變成output數組, 需要三組輪換：

1. a[0]-&>a[1]-&>a[3]-&>a[6]-&>a[0]

2. a[2]-&>a[5]-a[2]

3. a[4]位置不變

完成每個輪換隻需要一個額外的變數，騰出一個數組位置。因此空間複雜度O(1)。每個元素只會被挪動一次，時間複雜度O(n)。

此外還需要標記哪些元素已經被移動過了。通常另開一個數組標記會比較方便。。但是這題不允許，所以可以把每個移動過的元素都加上一個很大的數作為標記，之後再還原。不過這樣做好像很傻...

大概演算法可能是這樣。。。

org_max = max(a)
shift = max(a) - min(a) + 1
for s in range(n):
if a[s] &> org_max: # this element is already moved
s += 1
continue

i = s
while True:
if i &< 2/n: j = 2 * i + 1 else: j = 2 * (n - 1 - i) a[j], tmp = tmp, a[j] a[j] += shift # mark as "moved" if j == s: break i = j s += 1 for s in range(n): if a[s] &> org_max: a[s] -= shift

#include &

int trans(int len, int i) {
if(len % 2 == 0) {
if(i &< len / 2) return i * 2 + 1; else return (len - i - 1) * 2; } else { if(i &< len / 2) return i * 2 + 1; else if(i &> len / 2) return (len - i - 1) * 2;
else return len - 1;
}
}

void swap(int *a, int *b) {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}

int main(void) {
int arr[] = {7, 6, 5, 4, 3, 2, 1};

//start
int len = sizeof(arr) / sizeof(*arr);
for(int i = 0; i &< len; i++) { if(arr[i] &> 0) {
int j = i, tmp = arr[i];
while(arr[j = trans(len, j)] &> 0) {
swap(tmp, arr[j]);
arr[j] = 0 - arr[j];
}
}
}
for(int i = 0; i &< len; i++) { arr[i] = 0 - arr[i]; } //print for(int i = 0; i &< len; i++) { printf("%d ", arr[i]); } }

和Coldwings一樣，假設數組全為正整數，便於使用負號標記

看一下簡單的交換，能總結出規律來。每輪只交換2次，交換完以後得到的是「有分界的2個有序數組」。

假設原數組為X：

a b c d e f g h i

對應的下標為

0 1 2 3 4 5 6 7 8

那麼第一次做的交換是：

  1. X[0] 《-----》 X[8]

  2. X[1] 《-----》 X[8]

也就是，先交換第一個和最後一個，再交換第二個和最後一個。

交換後的結果為

i a c d e f g h b

把已經交換好的結果不管（i和a），只看後面，

c d e f g h b

仍然是以h|b分開的有序數組。

現在的交換，是左邊從c開始

  1. X[2] &<----&> X[7]
  2. X[3] &<-----&> X[8]

交換完成後，結果是：

i a h b e f g c d

後面的efgcd又是以g|c為界的2個有序數組。這時要去掉前面4個

e f g c d

  1. X[4] &<----&> X[6]
  2. X[5] &<-----&> X[7]

可以看出，除了第一次交換的是8以外，後面的交換，左邊是順序下去，右邊也是順序下去。

直到左右碰上為止。

碰上以後，有2種情況：奇數個和偶數個。偶數個簡單，又開始一個遞歸的交換（但只排後面不排前面）。

奇數個，會遇到一個單獨的數。例如這裡的e比較獨特。等我想想再補充。

空間O1，時間On

=========================

如果是奇數，碰上時不需要2步交換，一步交換即可。

依次將每個數替換到正確的位置，即：

index &< n/2 ----&> 2*index

index &> n/2 ----&> 2*(n-index) - 1

index == n/2 ----&> n-1

用一個變數記錄x當前被覆蓋掉的元素，然後為x尋找正確的位置，直到形成一個環為止

void SeekPosForX(int x, int CurrentPos, int InitPos) {
if (CurrentPos == n/2)
CurrentPos = n-1;
else CurrentPos = CurrentPos &> n/2 ? 2*(n-CurrentPos)-1 : 2*CurrentPos;
// Find a cycle.
if (CurrentPos == InitPos) {a[InitPos] = -x; return;}
int tmp = a[CurrentPos];
// Make it negative to tag as replaced.
a[CurrentPos] = -x;
SeekPosForX(tmp,CurrentPos,InitPos);
}
void Solution(){
for (int i = 0; i &< n; ++i) { if (a[i] &< 0) continue; SeekPosForX(a[i], i, i); } for (int i = 0; i &< n; ++i) a[i] = -a[i]; }

int[] values = new int[]{7 , 6 , 5 , 4, 3, 2, 1};

int offset = values[values.length - 1] - 1;
for (int i = 0; i &< values.length; i++) { values[i] = (i % 2 == 0) ? (i / 2 + 1) : (values.length - (i - 1) / 2); values[i] += offset; } for (int i = 0; i &< values.length; i++) { System.out.print(values[i] + " "); }

import com.alibaba.fastjson.JSONObject;

public class Test {

public static void main(String[] args) {

int[] arr = new int[]{9,8,7,6,5,4,3,2,1};

int k = 1, i = arr.length-k++, j = 0;

int tmp = arr[i];

while(j &< arr.length) {

j = handle(arr, i, ++j, i, tmp);

i = arr.length-k++;

tmp = arr[i];

}

System.out.println(JSONObject.toJSONString(arr));

}

public static int handle(int[] arr, int i, int j, int k, int val) {

int h = hash(i, arr.length);

int tmp = arr[h];

arr[h] = val;

if(h != i h != k j &<= arr.length)

j = handle(arr, h, ++j, k, tmp);

return j;

}

public static int hash(int i, int len) {

return i &< len/2 ? i*2+1 : (len - i - 1)*2;

}

}

修改了下樣式

大致的寫一下PHP實現

$s=[];
for($i=10;$i&>0;$i--){$s[]=$i;}
$length = count($s);
$i=0;
$swap=0;
echo implode(",",$s),"

";
while($i&<$length){ if ($s[$i]&<0) {$i++;continue;} $target_index = ($i%2==0)?($length-1-($i/2)):floor($i/2); $j = $i; while($s[$target_index]&>0){
$swap=$s[$j];
$s[$j] = $s[$target_index] * -1;
$s[$target_index] = $swap;
echo $j," ",$target_index,"
";
echo implode(",",$s),"
";
$j = $target_index;
$target_index = ($j%2==0)?($length-1-($j/2)):floor($j/2);
if ($j == $target_index) break;
}
$i++;
}
foreach($s as $k=&>$v){
$s[$k] = abs($v);
}
echo implode(",",$s),"
";

int end = a.length - 1;

int begin = 0;

if(a.length==1){

System.out.print(a[0]);

}

for (int i = end; i &>= end / 2 + 1; i--) {

System.out.print(a[i]);

System.out.print(a[begin++]);

if (i == begin + 1) {

System.out.print(a[begin]);

}

}

好像被面過，當時思路是下面這樣，未必是最優方法，但反正面試過了…

從左1位置開始，如果當前位置的數放得不對，那麼先在這個位置放上對的數，然後把錯的這個數放到對的位置；對的位置在哪，顯然是由它原本所在的位置（它是第幾大的數）唯一確定的；如果對的位置上有另一個數，那麼繼續把這個數也放到它對的位置去；如此循環，直到某一次對的位置上已經有對的數在，說明兜了一圈回到了出發點。

不妨把上面的過程稱作一次兜圈。

那麼怎樣知道當前位置的數放得不對呢？當前位置的數如果經歷過了兜圈，就把這個數打上標記，比如，變成相對於整個數列最小數的相反數再減1（7變成-6，6變成-5...1變成0）；如果當前位置的數小於原數列的最小數，那麼它經歷了兜圈，已經處在對的位置。

兜了一圈回來，不代表所有數都被遍歷到，比如原題中的1764構成的一個群；那麼就要繼續遍歷，從上次兜圈的出發點的下一個位置開始；如果當前位置上的數已經被安放（其值小於最小數），自然略過。最後無圈可兜，從頭把數還原一遍。

每次兜圈，都會把一群的數放置到各自正確的位置。比如7654321，兜第一圈1764，兜第二圈25，兜第三圈3。

因為所有兜的圈所安置的數加起來也不超過n個，再加上從頭到尾過趟，所以總時間花費是O(n)。

至於上面說的打標記的方法，嚴格來講，正是這道題目真正複雜的地方。上面簡單假設最小數後面還留有空間給其他的數打標記，但數的分布決定了這件事的可行性。具體要如何存儲標記信息，請看其他答案吧。似乎還有更巧妙的方法，就不研究了。

具體思路：

先觀察換序前後的數組差異：

選用10個元素的數組已經足夠觀察了。

對於前5個元素，可以看出分別右移了1, 2, 3, 4, 5 個單位。

後面五個元素左移的數量不便觀察特點，所以依然選用右向。右向計數的話，顯然從倒數第一個開始比較方便，可以看出從右到左分別移動了 1, 4, 7, 10, 13 個單位。

下面觀察奇數個元素的數組：

第一種：

第二種：

可見中間的元素區分到前後兩組都可行，用第一種稍好一些。

因此，所有的數組都可以分為前後兩部分之後分別用等差數列表示移動單位的多少。可以看出，時間複雜度為 O(n) ，空間複雜度為 O(1) 是可以實現的。

換位的具體實現待更新，有時間了再補。

想了一下，思路是：先把原先的array進行兩兩配對，目的是讓最大和最小的，次大和次小的這樣的組合相鄰，比如：

  1. 第一步：［ 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 變為[ 11, 1, 9, 3, 7, 5, 6, 4, 8, 2, 10 ]，這樣配對之後，
  2. 第二步：再進行以兩個數為一對的重排，這個過程中同時可以把每個組裡面順序不一樣的交換一下，即為對［（11，1），（9，3），7，（6，5），（8，4），（10，2）］進行內部兩個交換（如果有必要），和外部重新排列

第一步的代碼：

var wavyArray = function(arr){
pairOrder(arr);
return arr;
};

// pairwise order
function pairOrder(arr){
var front=1, end=arr.length-1;
while(front&

第二部分實現起來稍微有點麻煩，考慮到需要兩兩一組，元素個數有奇數偶數情況。。但是可以抽象化為一個如［ 1，3，5，4，2］的array 重排成為 ［ 1，2，3，4，5］的情況，這種情況可以用兜圈的方法解決，即上面很多提到了，把元素放到正確的位置上然後一直放直到圈畫滿。

想了一下基本思路是這樣。。。

根據 @111qqz的思路

由於不能開一個新的數組保存記錄，所以對數據進行變換，將數據全部轉換為負數

本來為負數的值 減去數據中絕對值最大的數的絕對值

排序以後再把負數還原

def func(l):
n,b = len(l),-max(abs(min(l)),max(l))
position = lambda index:2*index+1 if index&0 else l[i]+b
for i in xrange(n):
if l[i] &> 0:
continue
index = i
next_index = position(index)
while index != next_index:
tmp = l[index]
l[index] = l[next_index]
l[next_index] = -tmp
next_index = position(next_index)
l[i] = -l[i]
for i in xrange(n):
if l[i] &> -b:
l[i] = -(l[i]+b)
return l

當然論演算法的話 @Eddium論文中的方法更好 但沒接觸過面試的時候應該想不到吧

std::vector& a;
size_t size = 7;
for (size_t i = 0; i &< size; i++) { a.push_back(size-i); } int next, k; for (size_t t = 0; t &< size; t++) { if (a[t] != size-t) { continue; } int j = -1; k = a[t]; for (size_t i = t;;) { next = (i%2==0)?(size-1-i/2):i/2; j = next; if (j==t) { a[i] = k; break; } a[i] = a[next]; i = j; } } for (int i = 0; i &< size; i++) { std::cout &<&< a[i] &<&< " "; } std::cout &<&< std::endl;

雖然是兩個for循環，但是的確時間是o(n)，空間是o(1),具體涉及群論。

for (int j=0 ;j&<=array.length;j+=2) { for(int k=j;k&

我想知道這到底是不是O(N)!!!.嚴格的來說不是的！！但是各位答主用的while。一個道理！都說自己是O（N）.那就算是On了吧

測試通過.

道理是這樣的

[7,6,5,4,3,2,1]-(第一次循環)&>[1,7,6,5,4,3,2]-（第二次）&>[1,7,2,6,5,4,3]......（第N/2次）

所以這也算是O（N）嗎 滑稽

推薦閱讀：

※如何計算std::vector的push_back方法插入一個對象的平均時間（要寫出計算式）？
※JDK源碼DualPivotQuicksort類中利用移位求除7近似值？
※一個與矩陣有關的演算法問題？
※將一個稀疏圖平均切分成 k 個子圖的時間複雜度是多少？

TAG:演算法 | 演算法與數據結構 |