Java: найдите K-й по величине элемент массива, используя 2 массива

Question

Вот описание алгоритма / решения:

• Входные данные: массив целых и индекс массива
• Выходные данные: K-й по величине элемент массива
• Считать первые K элементов во вспомогательный массив (самый большой из найденных K)
• Сортировать массив K-элементов

• Затем:

   for each remaining element {
      if (if it is smaller than the smallest element of the aux. array) {
          throw it away
      } else { 
          remove the current smallest element of the auxiliary array
          place the element into the correct position in the auxiliary array
      }
   }
  
   then return the smallest (the Kth) element of the auxiliary array
  

Я нашел следующее решение:

public int findElement() throws IndexingError {
    int[] bigArray = getArray();
    int k = getIndex();
    if (k <= 0 || k > bigArray.length) {
        throw new IndexingError();
    }

    int[] smallArray = Arrays.copyOfRange(bigArray,0,k-1);
    Arrays.sort(smallArray);


    for (int i = k; i < bigArray.length; i++) {
        for (int ii = 1; ii < smallArray.length; ii++) {
            smallArray[ii-1] = smallArray[ii];
            if (bigArray[i] > smallArray[ii]) {
                smallArray[ii] = bigArray[i];
                System.out.println(smallArray[ii] + " " + smallArray[ii-1] + " " + bigArray[i]);
                break;

            }
        }

    }

    return smallArray[0];
}

Так, например:

Код должен возвращать значение: 8, основываясь на информации ниже:

array = [2, 3, 8, 7, 1, 6, 5, 9, 4, 0]
k = 2

Запуск приведенного выше кода каждый раз приводит к различным выводам. Если вы запускаете его достаточно много раз, вы получаете правильный ответ?

Может ли кто-нибудь определить / исправить недостатки в моем коде?

Answer 1

Необходимо устранить следующие проблемы:

1. В методе Arrays.copyOfRange(array, from, to) индекс to является эксклюзивным.Таким образом, вам нужно иметь его как Arrays.copyOfRange(bigArray,0,k), чтобы скопировать первые k элементы во вспомогательный массив.
2. Логика, в которой вы перебираете оставшиеся элементы массива из основного массива и обновляете вспомогательный массивневерно.

Например, пусть вспомогательный массив будет: [4, 6], а следующий элемент основного массива будет 2.Согласно вашей логике вспомогательный массив будет обновлен до [6, 6], так как вы сначала копируете элемент с индексом 1 в индекс 0 во вспомогательном массиве, а затем проверяете, больше ли новый элемент (из основного массива), чемэлемент с индексом 1 во вспомогательном массиве.В этом случае новый элемент меньше, поэтому происходит только копирование, и мы получаем поврежденный вспомогательный массив.

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

public int findElement() throws IndexingError {
    int[] bigArray = getArray();
    int k = getIndex();
    if (k <= 0 || k > bigArray.length) {
        throw new IndexingError();
    }

    int[] smallArray = Arrays.copyOfRange(bigArray,0,k);
    Arrays.sort(smallArray);


    for (int i = k; i < bigArray.length; i++) {
        if(bigArray[i] > smallArray[0]) {
            smallArray[0] = bigArray[i];
            int j = 0;
            while((j < k-1) && (smallArray[j] > smallArray[j+1])) {
                swap(smallArray[j], smallArray[j+1]);
                j++;
            }
        }

    }

    return smallArray[0];
}