webentwicklung-frage-antwort-db.com.de

Median einer Matrix mit sortierten Zeilen

Ich kann das folgende Problem nicht optimal lösen und finde nirgendwo einen Ansatz.

Bestimmen Sie in einer N × M-Matrix, in der jede Zeile sortiert ist, den Gesamtmittelwert der Matrix. Angenommen, N * M ist ungerade.

Zum Beispiel, 

Matrix =
[1, 3, 5]
[2, 6, 9]
[3, 6, 9] 

A = [1, 2, 3, 3, 5, 6, 6, 9, 9] 

Der Medianwert ist 5. Wir geben also 5 zurück.
Hinweis: Es ist kein zusätzlicher Speicher zulässig.

Jede Hilfe wird geschätzt.

10
hatellla

Betrachten Sie den folgenden Prozess.

  • Wenn wir die N * M-Matrix als 1-D-Array betrachten, ist der Median das Element des 1+N*M/2-ten Elements.

  • Dann ist x der Median, wenn x ein Element der Matrix ist und die Anzahl der Matrixelemente ≤ x gleich 1 + N*M/2 ist.

  • Da die Matrixelemente in jeder Zeile sortiert sind, können Sie leicht die Anzahl der Elemente in jeder Zeile less than or equals x finden. Für das Finden in der gesamten Matrix ist die Komplexität N*log M bei binärer Suche.

  • Finden Sie dann zuerst das Minimum und Maximum Element aus der N * M-Matrix. Wenden Sie die binäre Suche in diesem Bereich an und führen Sie die obige Funktion für jedes x aus.

  • Wenn die Anzahl der Elemente in der Matrix ≤ x1 + N*M/2 ist und x in dieser Matrix enthalten ist, ist x der Median.

Sie können dies unter C++ Code betrachten: 

int median(vector<vector<int> > &A) {
    int min = A[0][0], max = A[0][0];
    int n = A.size(), m = A[0].size();
    for (int i = 0; i < n; ++i) {
        if (A[i][0] < min) min = A[i][0];
        if (A[i][m-1] > max) max = A[i][m-1];
    }

    int element = (n * m + 1) / 2;
    while (min < max) {
        int mid = min + (max - min) / 2;
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            cnt += upper_bound(&A[i][0], &A[i][m], mid) - &A[i][0];
        if (cnt < element)
            min = mid + 1;
        else
            max = mid;
    }
    return min;
}
11
sunkuet02

Wenn die Matrixelemente Ganzzahlen sind, kann man den Median binär suchen, beginnend mit dem Matrixbereich für hi und low. O (n log m log (hi-low)).

Ansonsten besteht eine Möglichkeit, die O (n²log²m) -Wost-Fall-Zeitkomplexität aufweist, in der binären Suche O (log m) für jede Zeile, O (n), dem nächsten Element zum Gesamtmatrix-Median von links und dem am nächsten von rechts, O (n log m), Aktualisierung der besten bisher. Wir wissen, dass der Gesamt-Median nicht mehr als floor(m * n / 2)-Elemente enthält, die strikt weniger als er sind, und dass das Hinzufügen der Anzahl der Elemente und der Anzahl der Elemente, die es auftritt, nicht weniger als floor(m * n / 2) + 1 sein kann. Wir verwenden die standardmäßige binäre Suche in der Zeile und überspringen - wie Greybeard darauf hinweist - den Test auf Elemente außerhalb unseres 'besten' Bereichs. Bei der Prüfung, wie nahe ein Element am Median liegt, wird gezählt, wie viele Elemente in jeder Zeile strikt darunter liegen und wie viele gleich, was in O(n log m) time mit n binären Suchen erreicht wird. Da die Zeile sortiert ist, wissen wir, dass größere Elemente mehr "nach rechts" und geringere Elemente mehr "nach links" im Verhältnis zum Gesamtmittelwert sind.

Wenn die Matrix neu angeordnet werden darf, ist die Zeitkomplexität von O (mn log (mn)) möglich, indem die Matrix an Ort und Stelle sortiert wird (z. B. mit Block-Sortierung) und das mittlere Element zurückgegeben wird.

1

Es gibt einen randomisierten Algorithmus, der dieses Problem in der Zeit O (n (log n) (log m)) löst. Es handelt sich um einen Las Vegas-Algorithmus , was bedeutet, dass er immer korrekte Ergebnisse liefert, aber möglicherweise länger dauert als erwartet. In diesem Fall ist die Wahrscheinlichkeit, dass es viel länger dauert als erwartet, äußerst gering.

Wenn m = 1, reduziert sich dieses Problem auf das Problem, den Median in einem schreibgeschützten Array mit konstantem Speicherplatz zu finden. Dieses Problem hat keine bekannte optimale Lösung: siehe "Ermittlung des Medians im Nur-Lese-Speicher bei Ganzzahl-Eingaben, Chan et al."

Eine merkwürdige Sache über diese Verringerung des Problems bei m = 1 ist, dass dieser sub -Fall auch ein super -Fall ist, indem ein Algorithmus für m = 1 auf den m> 1-Fall angewendet werden kann. Die Idee ist, einfach zu vergessen, dass die Arrayzeilen sortiert sind und den gesamten Speicherbereich als unsortiertes Array der Größe n * m behandeln. So ist zum Beispiel der triviale Algorithmus für den Fall m = 1, bei dem jedes Element darauf geprüft wird, ob es sich um den Median handelt, O (n. 1)2) Zeit. Anwenden, wenn m> 1 O (n2m2) Zeit.

Zurück zum Fall m = 1 im Vergleichsmodell (in dem die Elemente des Arrays Ganzzahlen, Strings, reelle Zahlen oder alles andere sein können, das mit den Ungleichheitsoperatoren "<", ">" verglichen werden kann), die bekannteste deterministische Lösung, die Leerzeichen verwendet, s (wobei s eine Konstante ist, dh in O(1)) hat Zeit ϴ (2ss! n1 + 1/s), und es ist komplexer als die üblichen Algorithmen, die in stackoverflow diskutiert werden (allerdings nicht unter https://cstheory.stackexchange.com oder https://cs.stackexchange.com ). Es verwendet eine verkettete Folge von Algorithmen As, EINs-1, ..., EIN1, wo eins + 1 ruft A ans. Sie können es in "Auswahl aus dem Nur-Lese-Speicher und Sortieren mit minimaler Datenbewegung" durch Munro und Raman lesen.

Es gibt einen einfachen randomisierten Algorithmus mit geringerer Laufzeit und hoher Wahrscheinlichkeit. Für jede Konstante c läuft dieser Algorithmus in der Zeit O (n log n) mit der Wahrscheinlichkeit 1 - O (n-c). Wenn das Array die Matrix der Größe n * m ist, ergibt sich O (nm Log (nm)).

Dieser Algorithmus ähnelt der Schnellauswahl sehr, ohne dass Elemente während der Partitionierung neu angeordnet werden müssen.

import random

def index_range(needle, haystack):
  """The index range' of a value over an array is a pair
  consisting of the number of elements in the array less
  than that value and the number of elements in the array
  less than or equal to the value.
  """
  less = same = 0
  for x in haystack:
    if x < needle: less += 1
    Elif x == needle: same += 1
  return less, less + same

def median(xs):
  """Finds the median of xs using O(1) extra space. Does not
  alter xs.
  """
  if not xs: return None
  # First, find the minimum and maximum of the array and
  # their index ranges:
  lo, hi = min(xs), max(xs)
  lo_begin, lo_end = index_range(lo, xs)
  hi_begin, hi_end = index_range(hi, xs)
  # Gradually we will move the lo and hi index ranges closer
  # to the median.
  mid_idx = len(xs)//2
  while True:
    print "range size", hi_begin - lo_end
    if lo_begin <= mid_idx < lo_end:
      return lo
    if hi_begin <= mid_idx < hi_end:
      return hi
    assert hi_begin - lo_end > 0
    # Loop over the array, inspecting each item between lo
    # and hi. This loops sole purpose is to reservoir sample
    # from that set. This makes res a randomly selected
    # element from among those strictly between lo and hi in
    # xs:
    res_size = 0
    res = None
    for x in xs:
      if lo < x < hi:
        res_size += 1
        if 1 == random.randint(1, res_size):
          res = x
    assert res is not None
    assert hi_begin - lo_end == res_size
    # Now find which size of the median res is on and
    # continue the search on the smaller region:
    res_begin, res_end = index_range(res, xs)
    if res_end > mid_idx:
      hi, hi_begin, hi_end = res, res_begin, res_end
    else:
      lo, lo_begin, lo_end = res, res_begin, res_end

Es funktioniert, indem die oberen und unteren Grenzen des Medianwerts beibehalten werden. Anschließend durchläuft es das Array und wählt zufällig einen Wert zwischen den Grenzen aus. Dieser Wert ersetzt eine der Grenzen und der Prozess beginnt von neuem.

Die Grenzen werden von ihrem Indexbereich begleitet, ein Maß dafür, bei welchen Indizes die Grenze erscheinen würde, wenn das Array sortiert wäre. Sobald eine der Grenzen am Index ⌊n/2⌋ erscheint, ist dies der Median und der Algorithmus endet.

Wenn ein Element zufällig in der Lücke zwischen den Grenzen ausgewählt wird, verringert sich die Lücke um 50%. Der Algorithmus endet (spätestens), wenn die Lücke 0 ist. Wir können dies als eine Reihe von zufällig unabhängigen, gleichmäßig verteilten Variablen X modellierenich von (0,1), so dass Yk = X1 * X2 * ... * Xk wo Xich ist das Verhältnis der Lücke, die nach der Runde i verbleibt. Wenn beispielsweise nach der zehnten Runde die Lücke zwischen den Indexbereichen von lo und hi 120 ist und nach der elften Runde die Lücke 90 ist, dann ist X11 = 0,75. Der Algorithmus endet, wenn Yk <1/n, da der Abstand dann kleiner als 1 ist.

Wählen Sie eine konstante positive ganze Zahl k. Lassen Sie uns die Wahrscheinlichkeit, dass Yk log2n > = 1/n unter Verwendung von Chernoff-Grenzen. Wir haben Yk log2n = X1 * X2 * ... Xk log2nso l in Yk log2n = In X1 + ln X2 + ... + ln Xk log2n. Die Chernoff-Grenze ergibt dann Pr (ln X1 + ln X2 + ... + ln Xk log2n > = ln (1/n)) <= mint> 0 e-t ln (1/n) (E [et In X1] * E [et In X2] * ... * E [et In Xk log2 n]). Nach einiger Vereinfachung ist die rechte Seite mint> 0 nt (EX1t] * EX2t] * ... * EXk log2 nt]). Da dies ein Minimum ist und wir nach einer oberen Schranke suchen, können wir diese schwächen, indem wir uns auf t = 1 spezialisieren. Dann vereinfacht es sich zu n1-k, seit E [Xich] = 1/2.

Wenn wir zum Beispiel k = 6 wählen, begrenzt dies die Wahrscheinlichkeit, dass es 6 log gibt2n Runden oder mehr um n-5. Also mit der Wahrscheinlichkeit 1 - O (n-5) Der Algorithmus führt 6 log aus2n - 1 oder weniger Runden. Das meine ich mit "mit hoher Wahrscheinlichkeit" weiter oben.

Da jede Runde jedes Mitglied des Arrays eine konstante Anzahl von Malen überprüft, benötigt jede Runde eine lineare Zeit, mit einer hohen Gesamtlaufzeit von O (n log n). Wenn das Array nicht nur ein Array ist, sondern eine Matrix der Größe n * m, die auf O (nm Log (nm)) zutrifft.Wir können es jedoch wesentlich besser machen, indem wir die Sortierung der Zeilen nutzen. Als wir in einem einzelnen unsortierten Array arbeiteten, mussten wir die Elemente in der Lücke, auf die ich oben verwiesen habe, finden, um jedes Element des Arrays zu überprüfen. In einer Matrix mit sortierten Zeilen befinden sich die Elemente in der Lücke in einem zusammenhängenden Segment jeder Zeile. Jedes Segment kann mithilfe der binären Suche in der Zeit O (log m) identifiziert werden, sodass alle in der Zeit O (n log m) lokalisiert werden können. Die Probenahme des Reservoirs dauert jetzt O (n log m) Zeit pro Iteration der Schleife.

Die andere Hauptaufgabe in der Schleife besteht darin, den Indexbereich des Elements anhand der zufällig ausgewählten Lücke zu ermitteln. Da wiederum jede Zeile sortiert ist, kann der Indexbereich für das zufällig ausgewählte Element in einer Zeile in der Zeit O (log m) bestimmt werden. Die Summen der Indexbereiche für jede Zeile bilden den Indexbereich über das gesamte Array, sodass dieser Teil jeder Schleifeniteration auch nur O (n log m) Zeit benötigt.

.

-k) für jede Konstante k. Somit benötigt der gesamte Algorithmus O (n (log n) (log m)) Zeit mit hoher Wahrscheinlichkeit.import bisect import random def matrix_index_range(needle, haystack): """matrix_index_range calculates the index range of needle in a haystack that is a matrix (stored in row-major order) in which each row is sorted""" n, m = len(haystack), len(haystack[0]) begin = end = 0; for x in haystack: begin += bisect.bisect_left(x, needle) end += bisect.bisect_right(x, needle) return begin, end def matrix_median(xs): print "Starting" if not xs or not xs[0]: return None n, m = len(xs), len(xs[0]) lo, hi = xs[0][0], xs[0][m-1] for x in xs: lo, hi = min(lo, x[0]), max(hi, x[m-1]) lo_begin, lo_end = matrix_index_range(lo, xs) hi_begin, hi_end = matrix_index_range(hi, xs) mid_idx = (n * m) // 2 while True: print "range size", hi_begin - lo_end if lo_begin <= mid_idx < lo_end: return lo if hi_begin <= mid_idx < hi_end: return hi assert hi_begin - lo_end > 0 mid = None midth = random.randint(0, hi_begin - lo_end - 1) for x in xs: gap_begin = bisect.bisect_right(x, lo) gap_end = bisect.bisect_left(x, hi) gap_size = gap_end - gap_begin if midth < gap_size: mid = x[gap_begin + midth] break midth -= gap_size assert mid is not None mid_begin, mid_end = matrix_index_range(mid, xs) assert lo_end <= mid_begin and mid_end <= hi_begin if mid_end > mid_idx: hi, hi_begin, hi_end = mid, mid_begin, mid_end else: lo, lo_begin, lo_end = mid, mid_begin, mid_end

This solution is substantially faster than the first one when m is non-constant.

1
jbapple

Eine einfache O(1) - Speicherlösung besteht darin, zu prüfen, ob jedes einzelne Element z der Median ist. Dazu finden wir die Position von z in allen Zeilen, indem wir einfach die Anzahl der Elemente zusammenstellen, die kleiner sind als z . Dies nutzt nicht die Tatsache, dass jede Zeile sortiert ist, mit Ausnahme der Position von z in jeder Zeile in O (log M) time. Für jedes Element müssen wir N * log M Vergleiche machen, und es gibt N * M Elemente, also ist es N²M log M .

1
Saeed Amiri

Ich habe das O codiert (nlog2 m) Zeitlösung von גלעד ברקן, aber sie haben mich gebeten, den Code nicht zu ihrer Antwort hinzuzufügen, daher ist dies hier eine separate Antwort:

import bisect

def MedianDistance(key, matrix):
  lo = hi = 0
  for row in matrix:
    lo += bisect.bisect_left(row, key)
    hi += bisect.bisect_right(row, key)
  mid = len(matrix) * len(matrix[0]) // 2;
  if hi - 1 < mid: return hi - 1 - mid
  if lo > mid: return lo - mid
  return 0

def ZeroInSorted(row, measure):
  lo, hi = -1, len(row)
  while hi - lo > 1:
    mid = (lo + hi) // 2
    ans = measure(row[mid])
    if ans < 0: lo = mid
    Elif ans == 0: return mid
    else: hi = mid

def MatrixMedian(matrix):
  measure = lambda x: MedianDistance(x, matrix)
  for idx, row in enumerate(matrix):
    if not idx & idx-1: print(idx)
    ans = ZeroInSorted(row, measure)
    if ans is not None: return row[ans]
1
jbapple

sunkuet02s Antwort mit Verfeinerungen und Python-Code:
Jede Zeile der N × M-Matrix A ist sortiert und hat ein mittleres Element, das ihren Median darstellt.
Es gibt mindestens N * (M + 1)/2 Elemente, die nicht größer als das Maximum hi dieser Medianen sind, und mindestens N * (M + 1)/2 nicht kleiner als das Minimum lo:
Der Median aller Elemente von A muss zwischen lo und hi einschließlich liegen.
Sobald mehr als die Hälfte der Elemente niedriger als der derzeitige Kandidat ist, ist bekannt, dass dieser hoch ist. Sobald zu wenige Zeilen übrig sind, damit die Anzahl der Elemente, die niedriger als der aktuelle Kandidat sind, die Hälfte der Gesamtzahl erreicht, ist der Kandidat bekanntermaßen niedrig: In beiden Fällen fahren Sie sofort mit dem nächsten Kandidaten fort.

from bisect import bisect

def median(A):
    """ returns the median of all elements in A.
        Each row of A needs to be in ascending order. """
    # overall median is between min and max row median
    lo, hi = minimax(A)
    n = len(A)
    middle_row = n // 2
    columns = len(A[0])
    half = (n * columns + 1) // 2
    while lo < hi:
        mid = lo + (hi - lo) // 2
        lower = 0
        # first half can't decide median
        for a in A[:middle_row]:
            lower += bisect(a, mid)
        # break as soon as mid is known to be too high or low
        for r, a in enumerate(A[middle_row:n-1]):
            lower += bisect(a, mid)
            if half <= lower:
                hi = mid
                break
            if lower < r*columns:
                lo = mid + 1
                break
        else: # decision in last row
            lower += bisect(A[n-1], mid)
            if half <= lower:
                hi = mid
            else:
                lo = mid + 1

    return lo


def minmax(x, y):
    """return min(x, y), max(x, y)"""
    if x < y:
        return x, y
    return y, x


def minimax(A):
    """ return min(A[0..m][n//2]), max(A[0..m][n//2]):
        minimum and maximum of medians if A is a
        row major matrix with sorted rows."""
    n = len(A)
    half = n // 2
    if n % 2:
        lo = hi = A[0][half]
    else:
        lo, hi = minmax(A[0][half], A[1][half])
    for i in range(2-n % 2, len(A[0]), 2):
        l, h = minmax(A[i][half], A[i+1][half])
        if l < lo:
            lo = l
        if hi< h:
            hi = h
    return lo, hi


if __=='__main__':
    print(median( [[1, 3, 5], [2, 6, 9], [3, 6, 9]] ))

(Ich halte std::upper_bound() und bisect.bisect() für gleichwertig (bisect_right() ist ein Alias).)
Für den zweiten kandidaten-Median kann die letzte verarbeitete Zeile niedriger sein als in der ersten Iteration. In folgenden Iterationen sollte diese Rownumber niemals sinken - zu faul, um dass in ((umbenennen und) middle_row entsprechend zu erhöhen).

0
greybeard

Las Vegas-Algorithmus verwenden:

from random import randint

def findMedian(matrix):
    #getting the length of columns and rows
     N = len(matrix)
     M = len(matrix[0])
     while True:
           counter = 0
           #select a row randomly
           u = randint(0,len(matrix)-1)
           #select a column randomly
           v = randint(0,len(matrix[0])-1)
           #random index
           x = matrix[u][v]
          for i in range(len(matrix)):
             for j in range(len(matrix[0])):
                 if matrix[i][j] < x:
                        counter+=1
          #finding median
          if counter == (N*M-1)//2:
     return (x)



 arr = [[1,3,5],
        [2,6,9],
        [3,6,9]]

 findMedian(arr)  
0
Eye Sun