給定n個元素的排序數組，在​​線性時間對子集n/2個元素進行排序

Question

我有一個有n個元素的有序數組。現在我給了n/2個元素，每個元素都屬於排序後的數組。 n/2元素是從排序後的數組中隨機獲取的。如何在線性時間對這些n/2元素進行排序？

Answer 1

一種方法涉及哈希。構建一個包含從數組中繪製的所有n/2個元素的散列集。如果允許重複，則改爲從元素到其頻率構建一個哈希表。根據預期，這將花費O（n）時間。

然後，按升序對已排序的數組進行迭代，並對數組的每個元素檢查它是否在散列集/散列表中。如果是這樣，請將該元素附加到輸出數組（如果允許重複，則在該元素的每個副本中執行一次）。這將花費O（1）次，根據期望，每個數組元素，因此這一步也需要時間O（n）。

因此，根據期望，總運行時間爲O（n）。

希望這會有所幫助！

Answer 2

如果這些元素放入一個數組，你可以使用另一個布爾數組，這標誌着什麼元素已經所以通過這個數組走路選擇boolean [] selected

，只打印出已被標記爲選擇的元素，你可以獲得理想的效果。

編輯：由裝飾返回的對象，我們甚至可以排序的隨機值

boolean [] selected; 
Object [] data;// the array of elements 

ReturnObject getRandom(){ 
    int index = random(); 
    selected[index] = true; 
    return new ReturnObject(index,data[index]); 
} 

void printSelected(){ 

    for(int i = 0; i < data.length; i++){ 
     if(selected[i]){ 
      print(data[i]); 
     } 
    } 
} 

void printSubset(ReturnObject[]set){ 
    boolean []selected = .... 
    for(int i = 0; i < set.length; i++){ 
     selected[set[i].index] = true; 
    } 
    for(int i = 0; i < data.length; i++){ 
     if(selected[i]){ 
      print(data[i]); 
     } 
    } 
} 


class ReturnObject{//Class decorating the return object, which includes its index in the data array 
    int index; 
    Object data; 
}