Как найти k-е наименьшее целое число в несортированном массиве без сортировки массива?

Question

Итак, мне дан (несортированный) массив A из N различных целых чисел, я пытаюсь реализовать алгоритм «разделяй и властвуй», чтобы найти в массиве K-й наименьший элемент (K ≤ N) (т.е. это будетв целом наименьшее, если К = 1).Алгоритм возвращает значение K-го наименьшего элемента в массиве.Мне нужно, чтобы он запускался за O (N) время в среднем случае.Кто-нибудь может дать мне несколько советов?

Answer 1

Сефи, я собираюсь пройти через это очень осторожно.Вы всегда должны быть осторожны, помогая людям с алгоритмами, потому что, и я не могу этого подчеркнуть, решение проблем алгоритма для программистов - то же самое, что поднятие тяжестей для профессиональных спортсменов .Знание того, как привести себя в режим мышления, как компьютера, - это то, за что вам заплатят через несколько лет.Так что, если решения вам только что дадут, вы будете парнем, который отскакивает от работы к работе каждые 6 месяцев, а не парнем, который становится ведущим разработчиком или уходит сам с успешной компанией.

Теперь, когда эта разглагольствования не существует ...

Традиционно мы думаем об алгоритмах, которые циклически обходят массив, и по-разному повторяют его в зависимости от первого результата и повторяют до тех пор, покавыполнены некоторые условия, чтобы быть O (n ^ 2).Вещи, которые соответствуют этому критерию, это сортировка выбора, вставка и пузырьковая сортировка.

Но это не обязательно.Если мы сможем правильно разделить массив на сегменты и доказать размер этих сегментов, мы сможем сохранить его в низком порядке.

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

Let A be an array of size N with N distinct elements in it.

Let M be the element that resides at A[N/2]

Let A-large be an array of all elements greater than M.
Let A-small be an array of all elements less than M.

Что мы знаем об A-small и A-large?Они одинакового размера?Может быть, но, вероятно, нет.

Является ли size(A-small) > k?или это < k?

Если size(A-small) == k - 1, не сделает ли это М самым маленьким k-м элементом?

Есть ли что-то, что мы можем сделать, чтобы создать новое значение для k и сделатькакое-нибудь повторение здесь?

Я не собираюсь заканчивать это для вас, потому что должно быть много, чтобы пережевать.Это те вопросы, которые вам нужно задать себе.@templatetypedef на 100% на правильном пути, он только расширяется.

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

Answer 2

В качестве подсказки подумайте о том, как работает шаг раздела быстрой сортировки.Он разбивает входные данные таким образом, что ось находится в своем окончательном положении, самые маленькие элементы находятся слева, а более крупные элементы - справа.Учитывая эту информацию и зная, какой индекс вы пытались найти, можете ли вы придумать способ рекурсивного поиска k-го элемента?

Answer 3

import java.util.Scanner;


public class JavaApplication1 {
 public static int findpivot(int a,int b,int c){
     //System.out.println("x");
      if(a > b){
        if(c > a){
            return a;
        }
        else if(c > b){
            return c;
        }
        else{
            return b;
        }
    }
    else{
        if(c > b){
            return b;
        }
        else if(c > a){
            return c;
        }
        else{
            return a;
        }
    }
}

public static void find(int arr[],int l,int r,int target){
    //System.out.println(1);
    if(l >= r){
        return;
    }
    int mid = (l+r)/2;
       // System.out.println(1);
    int pivot = findpivot(arr[mid],arr[l],arr[r]);
    int i = l;
    int j = r;
    while(i<=j){
        while(arr[i] < pivot)i++;
        while(arr[j] > pivot)j--;
        if(i<=j){
            int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;//
            i++;
            j--;
        }

    }
    if(target <= (i-1)){
        find(arr,0,i-1,target);
    }
    else{
        find(arr,i,r,target);
    }
}

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            int arr[] = new int[n];
            for(int i = 0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            int k = sc.nextInt();
            find(arr,0,n-1,k-1);
            System.out.println(arr[k-1]);
        }

    }

}

Время Complexcity почти O (N).

Answer 4

попробуйте найти алгоритм выбора или алгоритм сортировки выбора

Answer 5

Для таких классических задач википедия работает очень хорошо ... См. Алгоритм выбора в википедии

Answer 6

Подсчет вхождений каждого целого числа в массиве в другом массиве.