kthSmallest yöntemi, tamsayıların bir dizisi/alt dizisi

Question

sonunda pivot ile iki bölüm ayrıldığında, bölümleme yöntemimin çalıştığını düşünüyorum, ancak kthSmallest yöntemini nasıl anlayacağımı veya anlayamıyorum. Artık bölümleme yöntemimle sınır hatalarından kurtulmayacağım, ki bu bana çalışmanın ve çalışmanın test edildiği gibi olduğunu düşünmeme yol açıyor. Ancak, kthSmallest yöntemim genellikle sonsuz bir döngüde sıkışır ve bir değer döndürdüğünde, hiçbir zaman doğru değer değildir.

İki alt aralık arasında pivot yerleştiren çevrimiçi örnekleri gördüm ancak ödevimiz için pivot her zaman en sonunda sonunda bu örneklere bakarken kafam karışıyor. Bu Yapmaya çalıştığınız ne gibi görünüyor

class Median{ 
    static int kthSmallest(int[] arr, int left, int right, int k){ 
     int divider = partition(arr, left, right); 
     if(divider == k-1){ 
      return arr[right]; 
     } 
     else if(divider > k-1){ 
      return kthSmallest(arr, left, divider-1, k); 
     } 
     else{ 
      return kthSmallest(arr, divider, right, (k - divider-1)); 
     } 
    } 

    static int partition(int[] arr, int left, int right){ 
     int pivot = arr[right]; 
     int index = left; 
     for(int i = left; i < right-1; i++){ 
      if(arr[i] < pivot){ 
       swap(arr, index, i); 
       index++; 
      } 
     } 
     printArr(arr); 
     System.out.println("divider: " + index); 
     return index; 
    } 

    static void swap(int[] arr, int i, int j){ 
     int temp = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = temp; 
    } 

    static void printArr(int[] arr){ 
     System.out.println(); 
     for(int index = 0; index < arr.length - 1; index++){ 
      System.out.print(arr[index] + ", "); 
     } 
     System.out.print(arr[arr.length-1]); 
     System.out.println(); 
    } 

    public static void main(String[] args){ 
     int[] arr = {34,-1,0,5,3}; 
     printArr(arr); 
     //System.out.println(partition(arr, 0, arr.length-1)); 
     //printArr(arr); 
     System.out.println(kthSmallest(arr, 0, arr.length - 1, 2)); 

    } 

} 

Answer 1

QuickSelect algoritmasını uygulamak, bu yüzden Wikipedia article bir göz atmanızı öneririz: Burada

ben ne var.

Kodunuza baktığımda, "sonunda" pimi yanlış yorumladığınıza inanıyorum. İhtiyaçlarınızın ne istediğine inanıyorum, 'u pivot'u sondan seçin ve sonra iki alt listenin arasına yerleştirin, böylece listeniz doğru görünüyor. Örneğin,

34 -1 0 5 3

pivot işini yapmıyor

değil

-1 0 34 5 3

-1 0 3 34 5

doğru haline gelmelidir.

kthSmallest yönteminizde birkaç sorun da var. Yinelemede geçirdiğiniz değerleri iki kez kontrol edin ve aynı zamanda sınırsız tekrarlamaya neden olabilecek bir vakayı da kaçırdınız. Kesinlikle takılıp kalırlar için spoiler: '(- bölücüyü -1 k)' sadece k için listeyi endekslemek yeniden olmadığı için

Sen, değiştirmek gerekir.

left == right Eğer gereksiz yineleme alırsanız, bu durumda geri dönmeniz gerekir.

Sizin partition yönteminizde, bölümlendirmekte olduğunuz listenin yeterince uzağında yinelediğinizden emin olun. Yine, her ihtimale karşı gerçekten yanıt bulamadıysanız:

for(int i = left; i < right-1; i++) teşekkür ederim YAY for(int i = left; i <= right-1; i++)