Выберите самый маленький элемент из массива

Question

У меня есть метод «разделяй и властвуй», чтобы найти i-й наименьший элемент из массива.Вот код:

public class rand_select{
    public static int Rand_partition(int a[], int p, int q, int i) {
        //smallest in a[p..q]
        if ( p==q) return a[p];
        int r=partition (a,p,q);
        int k=r-p+1;
        if (i==k) return a[r];
        if (i<k){
            return Rand_partition(a,p,r-1,i);
        }
        return Rand_partition(a,r-1,q,i-k);
    }

    public static void main(String[] args) {
        int a[]=new int []{6,10,13,15,8,3,2,12};
        System.out.println(Rand_partition(a,0,a.length-1,7));
    }

    public static  int partition(int a[],int p,int q) {
        int  m=a[0];
        while (p < q) {
            while (p < q && a[p++] < m) {
                p++;
            }
            while (q > p && a[q--] > m) {
                q--;
            }
            int t = a[p];
            a[p] = a[q];
            a[q] = t;
        }
        int k=0;
        for (int i=0; i < a.length; i++) {
            if ( a[i]==m){
                k=i;
            }
        }
        return k;
    }
}

Однако, я получаю исключение при запуске: java.lang.ArrayIndexOutOfBoundsException.

Answer 1

Мне удалось исправить несколько ошибок. Незначительный является этой строкой:

  return Rand_partition(a,r-1,q,i-k);
                           ^

Вместо этого вы хотите это:

  return Rand_partition(a,r+1,q,i-k);
                           ^

Это потому, что вы разбили a[p..q] на три части следующим образом:

  a[p..r-1], a[r], a[r+1..q]

Ваш исходный код прекрасно обрабатывает регистр a[r] и a[p..r-1], но портит a[r+1..q], используя вместо него r-1.

---

Мне также удалось исправить и упростить partition:

public static  int partition(int a[],int p,int q){
    int  m=a[p]; // not m[0], you want to partition m[p..q]!!!
    while ( p<q){
        while (p<q && a[p] <m){ // don't do p++ here!
            p++;
        }
        while (q>p && a[q]>m){ // don't do q-- here!
            q--;
        }
        int t=a[p];
        a[p]=a[q];
        a[q]=t;
    }
    return p; // no need to search!!!
}

Ваш исходный код содержал посторонние p++ и q--. Кроме того, поиск, где находится стержень, не нужен. Это где p и q встречаются.

---

Об соглашениях по присвоению имен

Пожалуйста, соблюдайте Соглашения об именах Java :

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

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

• Как это утверждение имеет смысл? (Соглашение об именовании Sun для переменных Java)
  • К сожалению, приведенный выше документ соглашения об именах содержит одну явную ошибку

---

В объявлениях массива

Кроме того, не создавайте привычку объявлять массивы следующим образом:

int x[];

Вместо скобок следует использовать тип , а не идентификатор :

int[] x;

Похожие вопросы

• Есть ли разница между Object[] x и Object x[]?
• Разница между int[] myArray и int myArray[] в Java
• в объявлении массива int[] k,i и int k[],i
  • Эти объявления приводят к различным типам i!

Answer 2

Предполагая, что это не домашняя работа, где вам нужно сделать это таким образом, и она не находится на критическом пути (что является вероятным предположением), просто отсортируйте массив и возьмите значение по индексу i.

public static getIthSmallest(final int[] myArray, final int i) {
    if (i < 0) {
        System.err.println("You're going to get an ArrayIndexOutOfBoundsException.");
    }
    if (i >= myArray.length) {
        System.err.println("You're going to get an ArrayIndexOutOfBoundsException.");
    }
    Arrays.sort(myArray);
    return myArray[i];
}

Answer 3

Понятия не имею, в чем ваша ошибка (мне не нравится Java:)

Простое решение (O(n) среднее, O(n^2) наихудший случай) этой проблемы состоит в том, чтобы скопировать источник в красивую простую реализацию qsort и сделать его рекурсивным только на той стороне, которая содержит позицию, которая вас интересует. Это должно быть около 5 строк кода, поэтому это должно быть легко сделать.

Если я маленький, есть решение O(n + log(n)*i*log(i))):

int FindI(int[] array, int i)
{
    int[] tmp = array[0..i].dup; // copy first i elements;

    sort(tmp);                   // sort, low to high

    foreach(j in array[i..$])    // loop over the rest
       if(j < tmp[0])
       {
          tmp[0] = j;
          sort(tmp);
       }
    return tmp[0];
}

Answer 4

Алгоритм, который вы пытаетесь реализовать, называется Быстрый выбор . Здесь - ссылка на рабочий код, использующий стратегию разбиения на медиану-три.

Answer 5

Вы можете использовать общедоступные статические T мин (сборник сборов, компараторный комп) в сборник .