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

1樓：納尼思密達

import com.alibaba.fastjson.JSONObject;

public class Test ;

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;

2樓：那把殺豬刀

修改了下樣式

大致的寫一下PHP實現

$s=;

for($i=10;$i>0;$i--)

$length = count($s);

$i=0;

$swap=0;

echo implode(',',$s),"\n\n\n";

while($i<$length)

$target_index = ($i%2==0)?($length-1-($i/2)):floor($i/2);

$j = $i;

while($s[$target_index]>0)$i++;

}foreach($s as $k=>$v)echo implode(',',$s),"\n";

3樓：歲寒友

int end = a.length - 1;

int begin = 0;

if(a.length==1)

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]);

4樓：陳莉莉

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

index < n/2 ----> 2*indexindex > n/2 ----> 2*(n-index) - 1index == n/2 ----> n-1用乙個變數記錄x當前被覆蓋掉的元素，然後為x尋找正確的位置，直到形成乙個環為止

void

SeekPosForX

(intx,

intCurrentPos

,int

InitPos

)int

tmp=a[

CurrentPos

];// Make it negative to tag as replaced.a[

CurrentPos]=

-x;SeekPosForX

(tmp

,CurrentPos

,InitPos);}

void

Solution

()for

(inti=

0;i

++i)a

[i]=

-a[i];}

5樓：

for(intj=

0;j<=

array

.length;j

+=2)}

public

void

swap

(inti,

intj

,int

array

)我想知道這到底是不是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）嗎滑稽

6樓：

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

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

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

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

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

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

因為所有兜的圈所安置的數加起來也不超過n個，再加上從頭到尾過趟，所以總時間花費是O(n)。至於上面說的打標記的方法，嚴格來講，正是這道題目真正複雜的地方。上面簡單假設最小數後面還留有空間給其他的數打標記，但數的分布決定了這件事的可行性。

具體要如何儲存標記資訊，請看其他答案吧。似乎還有更巧妙的方法，就不研究了。

7樓：

#include

inttrans

(int

len,

inti

)else

}void

swap

(int*a

,int*b

)int

main

(void);

//start

intlen

=sizeof

(arr)/

sizeof(*

arr);

for(

inti=0

)}}for

(inti=

0;i<

len;i++

)//print

for(

inti=0

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

8樓：

std::vector a;

size_t size = 7;

for (size_t i = 0; i < size; ia.push_back(size-i);

} int next, k;

for (size_t t = 0; t < size; tif (a[t] != size-tcontinueint j = -1;

k = a[t];

for (size_t i = tnext = (i%2==0)?(size-1-i/2):i/2;

j = next;

if (j==ta[i] = kbreaka[i] = a[next];

i = jfor (int i = 0; i < size; istd::cout << a[i] << "\t";

} std::cout << std::endl;

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

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

一道IT筆試題？

一道華為的筆試題，講一下思路？

一道演算法筆試題，各位大神幫幫看怎麼算好？

其他用戶還看了：

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

一道IT筆試題？

一道華為的筆試題，講一下思路？

一道演算法筆試題，各位大神幫幫看 怎麼算好？

其他用戶還看了：

一道演算法筆試題，各位大神幫幫看怎麼算好？