分而治之 - 未分類數組的k元素

鑑於未排序陣列Ťv []發現DE v [k]的該數組的元件如同陣列排序但不排數組v。

例如，如果K = 3和V = {2，-1，-6，7,4}該數組的第k元素爲。

由於我不能編輯傳遞的數組，我想不出另一種方式來排序數組而不保存在另一個局部變量上，或者嘗試像快速排序一樣分割數組，並返回最後一個元素的位置v應該是。

如果有幫助，這是我的代碼：

public static <T extends Comparable<? super T>> T kesimoRec(T v[], int izq, int der, int k) { 
    if(izq < der){ 
    int inf = izq-1; 
    T pivote = v[der]; 
     for(int i = izq; i < der; ++i){ 
      if(pivote.compareTo(v[i]) >= 0){ 
       ++inf; 
      } 
     } 
     ++inf; 
     if(inf > izq + k-1){ 
      return (kesimoRec(v, izq, inf-1, k)); 
     }else if(inf < izq + k-1){ 
      return (kesimoRec(v, inf+1, der, k-inf+izq-1)); 
     }else{ 
      return v[inf]; 
     } 
    }else{ 
     return v[der]; 
    } 
}

來源

2015-11-04 DaryEiki

是不是這個[quickselect（https://en.wikipedia.org/wiki/Quickselect）？ –

@MikeSamuel - 我感覺大多數快速選擇實現都是部分排序的。 – rcgldr

@rcgldr，是的，我認爲輸入已被修改。如果數組不是共享btw線程，你可能可以調整快速選擇在找到元素後保持不變。 –

爲什麼您使用分而治之？

我建議你使用PriorityQueue。你可以谷歌更多關於PriorityQueue。一旦你瞭解它的工作原理，你會發現很容易想出一個解決方案。我的Java代碼：

public class Solution { 
    public int findKthLargest(int[] nums, int k) { 
     PriorityQueue<Integer> queue = new PriorityQueue<Integer>(nums.length); 

     for (int num : nums) { 
      queue.offer(num); 
     } 

     for (int i = 0; i < nums.length - k; i++) { 
      queue.poll(); 
     } 

     return queue.peek(); 
    } 
}

嗯，對不起，我的解決辦法是找到第k個最大的，但你可以修改它找到的第k個最小的。

來源

2015-11-04 21:00:22 NMSL

我需要使用分而治之，因爲它是一種分而治之的運動，我知道有很多方法可以做到，但是謝謝你的建議。 – DaryEiki

@DaryEiki檢查此分支和征服解決方案鏈接：https：//leetcode.com/discuss/63971/a-consise-divide-and-conquer-solution – NMSL

@DaryEiki請注意，上述鏈接中的解決方案也是找到第k個最大的。 – NMSL

隨着分而治之

public static <T extends Comparable<? super T>> T kesimoRec(T v[], int izq, 
      int der, int k) { 
     if (izq == der) { 
      return v[izq]; 
     } 
     int pivote = partir(v, v[der], izq, der); 
     if (k == pivote) { 
      return v[k]; 
     } else if (k < pivote) { 
      return kesimoRec(v, izq, pivote - 1, k); 
     } else { 
      return kesimoRec(v, pivote + 1, der, k); 
     } 
    }

來源

2017-11-15 20:57:08 Monicalh

分而治之 - 未分類數組的k元素

回答

相關問題