Индекс массива разделов за пределами

Я пытаюсь реализовать рандомизированный алгоритм выбора, где массив заполняется случайными числами, и пользователь выбирает местоположение, и программа возвращает значение, совпадающее с местоположением в отсортированной версии массива без фактически сортируя массив.Индекс массива разделов за пределами

Проблема заключается в том, что программа дает ошибку массива из-за границы, и я считаю, что я правильно написал рандомизированные разделы и функции свопинга.

import java.util.*; 

public class RandomizedSelection { 

    public static void main(String[] args) { 
     int[] arr = new int[10]; 

     // fill array with random numbers between the range of 0-200 
     for (int i = 0; i < 10; i++) { 
      int n = (int)(java.lang.Math.random()*199); 
      arr[i] = n; 
     } 

     System.out.println("There is an array of 10 elements in the range" + 
          " of 0 - 200. Select a location to view" + 
          " the value."); 

     int loc = randomizedSelect(arr, 0, arr.length-1, 5); 

     System.out.println(loc); 

     System.out.println("The array was:\n" + Arrays.toString(arr)); 
    } 

    public static int randomizedSelect(int[] array, int start, int end, int i) { 
     if (start==end) 
      return array[start]; 

     int q = randomizedPartition(array, start, end); 
     int k = q - start + 1; 

     if (i == k) 
      return array[q]; 

     else if (i < k) 
      return randomizedSelect(array, start, q-1, i); 
     else 
      return randomizedSelect(array, q+1, end, i-k);  
    } 

    public static int randomizedPartition(int[] array, int start, int end) { 
     Random rand = new Random(System.currentTimeMillis()); 
     int pivotIdx = rand.nextInt(end - start + 1) + start; 
     int pivot = array[pivotIdx]; 

     swap(array, array[pivotIdx], array[end]); 

     System.out.println(Arrays.toString(array)); 
     pivotIdx = end; 

     int i = start - 1; 

     for (int j = start; j <= end-1; j++) { 
      if (array[j] <= pivot) { 
       i = i + 1; 
       swap(array, array[i], array[j]); 
      } 
     } 
     swap(array, array[i+1], array[pivotIdx]); 
     return i+1; 
    } 

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

Я не уверен, почему индекс за пределами границ. Мое предположение заключается в том, что когда он достигает последнего элемента в массиве, нет элемента для его замены. Это проблема? Как я могу это исправить? Я думал о том, чтобы просто разделить его на два массива, но я бы предпочел избежать этого.

источник

2014-10-15 Giovanni

У вас есть много индексов и даже не одна проверка привязки, это фабрика бедствия, особенно при использовании случайных индексов для массивов. – Maroun

Отлаживайте свой код, чтобы легко определить вашу проблему. – Maroun

Проверка пробелов автоматически в java. – Marichyasana

Ваш вызов для swap() передает содержимое массива в указанной позиции индекса, а не позицию индекса как для i, так и для j. Чтобы найти это все, что мне нужно сделать, был поставлен печати заявления в своп()

источник

2014-10-15 07:20:55 Marichyasana

Вы должны заменить

swap(array, array[pivotIdx], array[end]); 
swap(array, array[i], array[j]); 
swap(array, array[i+1], array[pivotIdx]);

swap(array, pivotIdx, end); 
swap(array, i, j); 
swap(array, i+1, pivotIdx);

Потому что, когда вы просите обмена, вы используете индекс, а не значение

источник

2014-10-15 07:28:07 yunandtidus

Индекс массива разделов за пределами

ответ

Смежные вопросы