Найдите n-й наименьший элемент в массиве

Пару дней назад я столкнулся с проблемой, в которой меня попросили найти n-й наименьший элемент в массиве. Это было отмечено как проблема среднего уровня, и это быстро заставило меня задуматься, почему это так сложно??? Просто отсортируйте массив, а затем верните значение, которое присутствует в индексе…

// This is assuming the nthSmallestIndex is within the array.
public int getNthSmallestElement(int[] array, int nthSmallestIndex) {
  Arrays.sort(array);
  return array[nthSmallestIndex];
}

Приведенный выше код кажется довольно элементарным, так почему же это проблема среднего уровня? Что ж, на мой вопрос ответили довольно скоро. Когда я запустил код, онлайн-редактор пожаловался, что мой код работает медленно. Для сортировки массива, диапазон которого полностью неизвестен, быстрее всего это можно сделать в O(n log n). Вопрос требовал, чтобы я завершил код за O (n) время.

Затем мне пришло в голову, что мне не нужно сортировать весь массив. Мне нужно только отсортировать массив до n-го наименьшего индекса. Так если у меня есть следующий массив [5, 2, 1, 4, 6, 3], и если мне нужно найти 2-е наименьшее число, мне просто нужно отсортировать первые 3 элемента.

Ну, я мог бы использовать раздел lomuto , чтобы выбрать элемент поворота и поместить его в правильный индекс и изменить порядок массива, где все элементы, меньшие, чем ось, находятся слева, а большие элементы справа. Давайте посмотрим, как реализован раздел lomuto.

public int lomutoPartition(int low, int high, int[] array) {
  int pivot = array[high], j = low;
  for (int i = low; i < high; i++) {
    if (array[i] < pivot) {
      int temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      ++j;
    }
  }
  int temp = array[high];
  array[high] = array[j];
  array[j] = temp;
  return j;
}

Поэтому, если у меня есть приведенный выше массив, и если я применю раздел lomuto, сохранив последний элемент в качестве стержня, я могу получить что-то вроде этого… [2, 1, 3, 6, 4, 5]. Обратите внимание, что 3 находится в нужном месте, а все элементы слева меньше 3, а элементы справа больше 3.

Теперь все, что мне нужно проверить, это то, что n-й наименьший индекс больше или меньше текущего значения, а затем продолжайте сортировать массив, пока я не достигну требуемого индекса. Затем меня осенило, что это быстрая сортировка с небольшой модификацией!!! Давайте взглянем на код…

public int getNthSmallestElement(int[] array, int nthSmallestIndex, int low, int high) {
  if (low < high) {
    int pivot = lomutoPartition(low, high, array);
    if (pivot == nthSmallestIndex) {
      return array[nthSmallestIndex];
    }
    if (nthSmallestIndex > pivot) {
      return getNthSmallestElement(array, nthSmallestIndex, pivot + 1, high);
    }
    return getNthSmallestElement(array, nthSmallestIndex, low, pivot - 1); 
  }
  return -1;
}

Теперь это решение в среднем случае получает n-й наименьший элемент за O (n) время. Позже, когда я выполнял поиск в Google, я обнаружил, что вышеупомянутое решение называется “Быстрый выбор”.

Я надеюсь, что этот пост помог вам понять, как найти n-й наименьший элемент за O (n) время (средний случай).)

Если вы хотите увидеть полную реализацию и другие подобные вопросы, ознакомьтесь с моим Репо на github.

Оригинал: “https://dev.to/vineeth/find-the-nth-smallest-element-in-an-array-2eam”