Создание массива медиан. Java

Question

У меня проблемы с поиском решения для этого упражнения:

Given scores, an array of integers representing all test and assignment scores, your task is to return an array of integers where output[i] represents the median grade after all marks up to (and including) scores[i] have been entered. Your instructor is a generous marker, so they always round the median up to the nearest integer.

median* - The median of an N-element sequence is defined as follows: If N is odd, the median is the element which stands in the middle of the sequence after it is sorted. If N is even, the median is the average (mean) of the two "middle" elements of the sequence after it is sorted.

Example

•For scores = [100, 20, 50, 70, 45] the output should be medianScores(scores) = [100, 60, 50, 60, 50].

After each score is entered, the median is recalculated as follows:
◦For [100], the median is 100 since it's the only element.
◦For [20, 100], the median is (20 + 100)/2 = 60 since there's an even number of elements.
◦For [20, 50, 100], the median is 50 (middle element).
◦For [20, 50, 70, 100], the median is (50 + 70)/2 = 60(mean of the two middle elements).
◦For [20, 45, 50, 70, 100], the median is 50 again (middle element).


Input / Output

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

 public static int[] getMedian(int[] arr){

    int[] sortedArr = new int[arr.length];
    int length = arr.length-1;
    int odd = arr.length-1;
    int even = arr.length-1;

    for(int i=0;i<arr.length;i++) {

        sortedArr[length] = arr[i];
        Arrays.sort(sortedArr);

        if (length % 2 == 0) {
            arr[i] = sortedArr[odd];
            odd--;
        } else {
            arr[i] = (sortedArr[even] + sortedArr[even - 1]) / 2;
            even--;
        }
        length--;
    }
return arr;

}

Алгоритм работает путем добавления элементов из arr в sortedArr. Элементы сортируются, а затем проверяется, является ли sortedArr четным или нечетным. Если его четное, arr [i] становится средним элементом, если нечетное, arr [i] - это сумма средних элементов, деленная на 2.

Я бы оценил вашу помощь.

Answer 1

Неоптимизированное решение.

Сначала необходимо просто вычислить медиану массива:

/** Generous or not: one to round up, zero to round down. */
private static final int generous = 1;

private static int median(int[] arr) {
    Arrays.sort(arr);
    int mid = arr.length / 2;
    if (mid + mid == arr.length) { // little optimized "is it even"
        return (arr[mid-1] + arr[mid] + generous) / 2;
    } else {
        return arr[mid];
    }
}

, а затем просто вызвать его для каждого подмассива:

// passed array will be (partially) sorted
private static int[] getMedian(int[] arr) {
    int[] result = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        result[i] = median(Arrays.copyOfRange(arr, 0, i+1));
    }
    return result;
}

---

Бит оптимизации: не создавайте подмассив, просто передайте длину, которую следует учитывать

private static int median(int[] arr, int len) {
    Arrays.sort(arr, 0, len);
    int mid = len / 2;
    if (mid + mid == len) { // little optimized "is it even"
        return (arr[mid-1] + arr[mid] + generous) / 2;
    } else {
        return arr[mid];
    }
}

в getMedian(), называемую

result[i] = median(arr, i+1);

Answer 2

Чтобы повысить эффективность, первым шагом является определение лучшего алгоритма.

Давайте назовем median[] созданный массив.

Я бы использовал две кучи:

• Максимальная куча left для самых низких значений k/2 или k/2+1 вплоть до k-го индекса, в зависимости k является четным или нечетным.
• Мин-куча right для самых высоких значений k/2 до k-го индекса

Затем

if k is even, median[k] = (left.max() + right.min())/2
if k is odd, median[k] = left.max()

Инициализация:

left <- min (scores[0], scores[1])
right <- max (scores[0], scores[1])

Затем для каждого нового значения x = scores[k] вы должны управлять двумя кучами, в зависимости от того, является ли k четным или нечетным, и в зависимости от сравнений между x, left.max() и * 1030. *. Важно, чтобы две кучи сохраняли правильные размеры. Это подразумевает, что иногда значение будет go из одной кучи в другую.

Если k четное (k-1 было нечетным):

If x < left.max() then x -> left, left.max() -> right (corresponding value removed from left)
else: x -> right

Если k нечетное:

If x < right.min() then x -> left
else: x -> right, right.min() -> left (corresponding value removed from right)

Глобальная сложность: O (nlogn)

Я не знаю java хорошо. Если у java нет кучи, я думаю, вы могли бы использовать PriorityQueue вместо этого.

Answer 3

Вы перезаписывали существующие значения при копировании массива в sortedArray.

    public static void main(String[] args) {
        int[] ret = getMedian(new int[]{100,20,50,70,45});
        System.out.println(Arrays.toString(ret));
    }

    public static int[] getMedian(int[] arr) {

        int[] sortedArr = new int[arr.length];
        int[] retArr = new int[arr.length];
        int len = 1;
        int realLength = arr.length-1;

        for (int i = 0; i < arr.length; i++) {

            sortedArr[realLength-i] = arr[i];
            Arrays.sort(sortedArr);
           // arrays are accessed in reverse so adjust is needed using
           // array length.
            if (len % 2 == 1) {
                // use middle value
                retArr[i] = sortedArr[realLength-len/2];
            } else {
                // average middle values 
                retArr[i] = (sortedArr[realLength-len/2]
                        + sortedArr[realLength-len/2 + 1]) / 2;
            }
            len++;
        }
        return retArr;
    }

}