阿裡巴巴有如下的筆試題目:
有一個神奇的數組,其中的第i個元素在排序之後的位置位於[i-k, i+k]之間(k序的).試寫算法把一個k序數組排序,要求最快.
解法,
顯然有以下幾個子序列:
X[0], X[k+1], X[2(k+1)], X[3(k+1)]......
X[1],X[k+1+1],X[2(k+1)+1],X[3(k+1)+1]......
........................
X[k],X[k+1+k],X[2(k+1)+k],X[3(k+1)+k]......
這k+1個子序列是已經排序好的,剩下的任務是把其歸並
有兩種方法:
方法一,
普通的merge,與把兩個數組歸並一樣的思想,則復雜度為O(nk)
方法二
用敗者樹,則合並一個元素要LogK的時間,合並n個元素要O(nlogk)的時間
解完.
