Ich habe Probleme, die Lösung für diese Übung zu finden:

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

Ich habe versucht, einen funktionierenden Code zu erhalten. Bisher funktioniert der Code, wenn die Länge eines Arrays ungerade ist, aber wenn es gerade ist, gibt es ein falsches Ergebnis zurück.

 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;

}

Der Algorithmus fügt Elemente von einem arr zu sortedArr hinzu. Die Elemente werden sortiert und es wird geprüft, ob sortiertArr gerade oder ungerade ist. Wenn es gerade ist, wird arr [i] das mittlere Element, wenn es ungerade ist, ist arr [i] die Summe der mittleren Elemente geteilt durch 2.

Ich würde Ihre Hilfe schätzen.

1
ArchibaldRajs 21 Feb. 2020 im 17:56

3 Antworten

Beste Antwort

Nicht optimierte Lösung.

Zuerst eine Methode, um nur den Median eines Arrays zu berechnen:

/** 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];
    }
}

Rufen Sie es dann einfach für jedes Sub-Array auf:

// 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;
}

Ein bisschen Optimierung: Erstellen Sie kein Sub-Array, sondern übergeben Sie nur die zu berücksichtigende Länge

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];
    }
}

In getMedian(), genannt als

result[i] = median(arr, i+1);
1
user85421-Banned 21 Feb. 2020 im 17:28

Sie haben vorhandene Werte beim Kopieren des Arrays nach sortedArray überschrieben.

    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;
    }

}

1
WJS 21 Feb. 2020 im 15:49

Um die Effizienz zu verbessern, besteht der erste Schritt darin, einen besseren Algorithmus zu bestimmen.

Nennen wir median[] das erstellte Array.

Ich würde zwei Haufen verwenden:

  • Ein Max-Heap left für die k/2 oder k/2+1 niedrigsten Werte bis zum k-ten Index, abhängig von k, ist gerade oder ungerade.
  • Ein Min-Heap right für die k/2 höchsten Werte bis zum k-ten Index

Dann,

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

Initialisierung:

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

Dann müssen Sie für jeden neuen Wert x = scores[k] die beiden Heaps verwalten, je nachdem, ob k gerade oder ungerade ist, und abhängig von den Vergleichen zwischen x, left.max() und right.min(). Es ist wichtig, dass zwei Haufen die richtige Größe haben. Dies impliziert, dass manchmal ein Wert von einem Heap zum anderen wechselt.

Wenn k gerade (k-1 war ungerade):

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

Wenn k ungerade:

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

Globale Komplexität: O (nlogn)

Ich kenne Java nicht gut. Wenn Java keine Haufen hat, könnten Sie stattdessen PriorityQueue verwenden.

1
Damien 21 Feb. 2020 im 16:53