Gegeben zwei Arrays; $birthseine Liste der Geburtsjahre enthält , die anzeigen , wenn jemand geboren wurde, und $deathseine Liste der Tod Jahren enthält , die anzeigen , wenn jemand gestorben ist , wie können wir das Jahr , an dem die Bevölkerung am höchsten war finden?

Zum Beispiel bei folgenden Arrays:

$births = [1984, 1981, 1984, 1991, 1996];
$deaths = [1991, 1984];

Das Jahr, in dem die Bevölkerung am höchsten war, sollte sein 1996, da die 3Menschen in diesem Jahr am Leben waren, was die höchste Bevölkerungszahl aller Jahre war.

Hier ist die laufende Mathematik dazu:

| Geburt | Tod | Bevölkerung |
| ------- | ------- | ------------ |
| 1981 | | 1 |
| 1984 | | 2 |
| 1984 | 1984 | 2 |
| 1991 | 1991 | 2 |
| 1996 | | 3 |

Annahmen

Wir können mit Sicherheit davon ausgehen, dass das Jahr, in dem jemand geboren wird, um eins zunehmen kann und das Jahr, in dem jemand stirbt, um eins zunehmen kann. In diesem Beispiel wurden 1984 2 Personen geboren und 1 Person starb 1984, was bedeutet, dass die Bevölkerung in diesem Jahr um 1 zunahm.

Wir können auch davon ausgehen, dass die Anzahl der Todesfälle niemals die Anzahl der Geburten überschreiten wird und dass kein Tod eintreten kann, wenn die Bevölkerung bei 0 liegt.

Wir können auch davon ausgehen, dass die Jahre in beiden $deathsund $birthsniemals negative oder Gleitkommawerte sind ( sie sind immer positive ganze Zahlen größer als 0 ).

Wir können jedoch nicht davon ausgehen, dass die Arrays sortiert werden oder dass es keine doppelten Werte gibt.

Bedarf

Wir müssen eine Funktion schreiben, um das Jahr zurückzugeben, in dem die höchste Population aufgetreten ist, wenn diese beiden Arrays als Eingabe verwendet werden. Die Funktion kann zurückkehren 0, false, "", oder NULL( jeder Wert akzeptabel Falsey ) , wenn die Eingabefelder leer sind oder wenn die Bevölkerung immer bei 0 gänzlich. Wenn die höchste Bevölkerung in mehreren Jahren aufgetreten ist, kann die Funktion das erste Jahr, in dem die höchste Bevölkerung erreicht wurde, oder ein nachfolgendes Jahr zurückgeben.

Zum Beispiel:

$births = [1997, 1997, 1997, 1998, 1999];
$deaths = [1998, 1999];

/* The highest population was 3 on 1997, 1998 and 1999, either answer is correct */

Darüber hinaus wäre es hilfreich , das Big O der Lösung einzubeziehen.

Mein bester Versuch, dies zu tun, wäre der folgende:

function highestPopulationYear(Array $births, Array $deaths): Int {

    sort($births);
    sort($deaths);

    $nextBirthYear = reset($births);
    $nextDeathYear = reset($deaths);

    $years = [];
    if ($nextBirthYear) {
        $years[] = $nextBirthYear;
    }
    if ($nextDeathYear) {
        $years[] = $nextDeathYear;
    }

    if ($years) {
        $currentYear = max(0, ...$years);
    } else {
        $currentYear = 0;
    }

    $maxYear = $maxPopulation = $currentPopulation = 0;

    while(current($births) !== false || current($deaths) !== false || $years) {

        while($currentYear === $nextBirthYear) {
            $currentPopulation++;
            $nextBirthYear = next($births);
        }

        while($currentYear === $nextDeathYear) {
            $currentPopulation--;
            $nextDeathYear = next($deaths);
        }

        if ($currentPopulation >= $maxPopulation) {
            $maxPopulation = $currentPopulation;
            $maxYear = $currentYear;
        }

        $years = [];

        if ($nextBirthYear) {
            $years[] = $nextBirthYear;
        }
        if ($nextDeathYear) {
            $years[] = $nextDeathYear;
        }
        if ($years) {
            $currentYear = min($years);
        } else {
            $currentYear = 0;
        }
    }

    return $maxYear;
}

Der obige Algorithmus sollte gegeben in Polynomzeit arbeiten ist es im schlimmsten Fall , O(((n log n) * 2) + k)wo nist die Anzahl der Elemente von jedem Array sortiert werden und kist die Anzahl der Geburt Jahre ( da wissen wir, dass kes immerk >= y ) , wo yZahl der Todes Jahre. Ich bin mir jedoch nicht sicher, ob es eine effizientere Lösung gibt.

Mein Interesse gilt lediglich einem verbesserten Big O der Rechenkomplexität gegenüber dem vorhandenen Algorithmus. Die Speicherkomplexität spielt keine Rolle. Auch die Laufzeitoptimierung ist nicht. Zumindest ist es kein Hauptanliegen . Kleinere / größere Laufzeitoptimierungen sind willkommen, aber hier nicht der Schlüsselfaktor.

Ich denke, wir können O(n log n)Zeit mit O(1)zusätzlichem Speicherplatz haben, indem wir zuerst sortieren und dann eine aktuelle Population und ein globales Maximum beibehalten, während wir iterieren. Ich habe versucht, das aktuelle Jahr als Bezugspunkt zu verwenden, aber die Logik schien immer noch etwas schwierig zu sein, daher bin ich mir nicht sicher, ob sie vollständig funktioniert hat. Hoffentlich kann es eine Vorstellung von dem Ansatz geben.

JavaScript-Code (Gegenbeispiele / Bugs willkommen)

function f(births, deaths){
  births.sort((a, b) => a - b);
  deaths.sort((a, b) => a - b);

  console.log(JSON.stringify(births));
  console.log(JSON.stringify(deaths));
  
  let i = 0;
  let j = 0;
  let year = births[i];
  let curr = 0;
  let max = curr;

  while (deaths[j] < births[0])
    j++;

  while (i < births.length || j < deaths.length){
    while (year == births[i]){
      curr = curr + 1;
      i = i + 1;
    }
    
    if (j == deaths.length || year < deaths[j]){
      max = Math.max(max, curr);
      console.log(`year: ${ year }, max: ${ max }, curr: ${ curr }`);
    
    } else if (j < deaths.length && deaths[j] == year){
      while (deaths[j] == year){
        curr = curr - 1;
        j = j + 1;
      }
      max = Math.max(max, curr);
      console.log(`year: ${ year }, max: ${ max }, curr: ${ curr }`);
    }

    if (j < deaths.length && deaths[j] > year && (i == births.length || deaths[j] < births[i])){
      year = deaths[j];
      while (deaths[j] == year){
        curr = curr - 1;
        j = j + 1;
      }
      console.log(`year: ${ year }, max: ${ max }, curr: ${ curr }`);
    }

    year = births[i];
  }
  
  return max;
}

var input = [
  [[1997, 1997, 1997, 1998, 1999],
  [1998, 1999]],
  [[1, 2, 2, 3, 4],
  [1, 2, 2, 5]],
  [[1984, 1981, 1984, 1991, 1996],
  [1991, 1984, 1997]],
  [[1984, 1981, 1984, 1991, 1996],
  [1991, 1982, 1984, 1997]]
]

for (let [births, deaths] of input)
  console.log(f(births, deaths));

Wenn der Jahresbereich min der Größenordnung von liegt n, können wir die Zählungen für jedes Jahr im Bereich speichern und haben O(n)zeitliche Komplexität. Wenn wir Lust haben wollten, könnten wir auch O(n * log log m)Zeitkomplexität haben, indem wir einen Y-schnellen Versuch verwenden , der eine O(log log m)zeitliche Nachfolge-Suche ermöglicht.

Wir können dies in linearer Zeit mit Bucket Sort lösen. Angenommen, die Größe der Eingabe ist n und der Bereich der Jahre ist m.

O(n): Find the min and max year across births and deaths.
O(m): Create an array of size max_yr - min_yr + 1, ints initialized to zero. 
      Treat the first cell of the array as min_yr, the next as min_yr+1, etc...
O(n): Parse the births array, incrementing the appropriate index of the array. 
      arr[birth_yr - min_yr] += 1
O(n): Ditto for deaths, decrementing the appropriate index of the array.
      arr[death_yr - min_yr] -= 1
O(m): Parse your array, keeping track of the cumulative sum and its max value.

Das größte kumulative Maximum ist Ihre Antwort.

Die Laufzeit beträgt O (n + m) und der zusätzlich benötigte Platz ist O (m).

Dies ist eine lineare Lösung in n, wenn m O (n) ist; dh wenn der Bereich der Jahre nicht schneller wächst als die Anzahl der Geburten und Todesfälle. Dies gilt mit ziemlicher Sicherheit für Daten aus der realen Welt.

Fassen Sie zuerst die Geburten und Todesfälle in einer Karte zusammen ( year => population change), sortieren Sie diese nach Schlüsseln und berechnen Sie die laufende Bevölkerung darüber.

Dies sollte ungefähr sein O(2n + n log n), wo nist die Anzahl der Geburten.

$births = [1984, 1981, 1984, 1991, 1996];
$deaths = [1991, 1984];

function highestPopulationYear(array $births, array $deaths): ?int
{
    $indexed = [];

    foreach ($births as $birth) {
        $indexed[$birth] = ($indexed[$birth] ?? 0) + 1;
    }

    foreach ($deaths as $death) {
        $indexed[$death] = ($indexed[$death] ?? 0) - 1;
    }

    ksort($indexed);

    $maxYear = null;
    $max = $current = 0;

    foreach ($indexed as $year => $change) {
        $current += $change;
        if ($current >= $max) {
            $max = $current;
            $maxYear = $year;
        }
    }

    return $maxYear;
}

var_dump(highestPopulationYear($births, $deaths));

Ich habe dieses Problem mit einem Speicherbedarf von O(n+m)[im schlimmsten Fall im besten Fall O(n)] gelöst.

und zeitliche Komplexität von O(n logn).

Hier n & msind die Länge birthsund deathsArrays.

Ich kenne kein PHP oder Javascript. Ich habe es mit Java implementiert und die Logik ist sehr einfach. Aber ich glaube, meine Idee kann auch in diesen Sprachen umgesetzt werden.

Technische Details:

Ich habe Java- TreeMapStruktur verwendet, um Aufzeichnungen über Geburten und Todesfälle zu speichern.

TreeMapFügt Daten sortiert ( schlüsselbasiert ) als (Schlüssel, Wert) Paar ein. Hier ist der Schlüssel das Jahr und der Wert die kumulierte Summe von Geburten und Todesfällen (negativ für Todesfälle).

Wir müssen keinen Todeswert einfügen, der nach dem höchsten Geburtsjahr aufgetreten ist.

Sobald die TreeMap mit den Aufzeichnungen zu Geburten und Sterbefällen gefüllt ist, werden alle kumulierten Summen aktualisiert und die maximale Bevölkerungszahl mit fortschreitendem Jahr gespeichert.

Beispielein- und -ausgabe: 1

Births: [1909, 1919, 1904, 1911, 1908, 1908, 1903, 1901, 1914, 1911, 1900, 1919, 1900, 1908, 1906]

Deaths: [1910, 1911, 1912, 1911, 1914, 1914, 1913, 1915, 1914, 1915]

Year counts Births: {1900=2, 1901=1, 1903=1, 1904=1, 1906=1, 1908=3, 1909=1, 1911=2, 1914=1, 1919=2}

Year counts Birth-Deaths combined: {1900=2, 1901=1, 1903=1, 1904=1, 1906=1, 1908=3, 1909=1, 1910=-1, 1911=0, 1912=-1, 1913=-1, 1914=-2, 1915=-2, 1919=2}

Yearwise population: {1900=2, 1901=3, 1903=4, 1904=5, 1906=6, 1908=9, 1909=10, 1910=9, 1911=9, 1912=8, 1913=7, 1914=5, 1915=3, 1919=5}

maxPopulation: 10
yearOfMaxPopulation: 1909

Beispielein- und -ausgabe: 2

Births: [1906, 1901, 1911, 1902, 1905, 1911, 1902, 1905, 1910, 1912, 1900, 1900, 1904, 1913, 1904]

Deaths: [1917, 1908, 1918, 1915, 1907, 1907, 1917, 1917, 1912, 1913, 1905, 1914]

Year counts Births: {1900=2, 1901=1, 1902=2, 1904=2, 1905=2, 1906=1, 1910=1, 1911=2, 1912=1, 1913=1}

Year counts Birth-Deaths combined: {1900=2, 1901=1, 1902=2, 1904=2, 1905=1, 1906=1, 1907=-2, 1908=-1, 1910=1, 1911=2, 1912=0, 1913=0}

Yearwise population: {1900=2, 1901=3, 1902=5, 1904=7, 1905=8, 1906=9, 1907=7, 1908=6, 1910=7, 1911=9, 1912=9, 1913=9}

maxPopulation: 9
yearOfMaxPopulation: 1906

Hier ereigneten sich Todesfälle ( 1914 & later) nach dem letzten Geburtsjahr 1913, wurden überhaupt nicht gezählt, was unnötige Berechnungen vermeidet.

Für insgesamt 10 millionDaten (Geburten und Todesfälle zusammen) und darüber 1000 years rangedauerte das Programm 3 sec.fast.

Wenn Daten gleicher Größe mit 100 years range, dauerte es 1.3 sec.

Alle Eingaben werden zufällig getroffen.

$births = [1984, 1981, 1984, 1991, 1996];
$deaths = [1991, 1984];
$years = array_unique(array_merge($births, $deaths));
sort($years);

$increaseByYear = array_count_values($births);
$decreaseByYear = array_count_values($deaths);
$populationByYear = array();

foreach ($years as $year) {
    $increase = $increaseByYear[$year] ?? 0;
    $decrease = $decreaseByYear[$year] ?? 0;
    $previousPopulationTally = end($populationByYear);
    $populationByYear[$year] = $previousPopulationTally + $increase - $decrease;
}

$maxPopulation = max($populationByYear);
$maxPopulationYears = array_keys($populationByYear, $maxPopulation);

$maxPopulationByYear = array_fill_keys($maxPopulationYears, $maxPopulation);
print_r($maxPopulationByYear);

Dies wird die Möglichkeit eines gebundenen Jahres berücksichtigen, sowie wenn ein Jahr des Todes einer Person nicht der Geburt einer Person entspricht.

In Bezug auf das Gedächtnis ist es zu behalten currentPopulationund zu currentYearberechnen. Das Sortieren von Arrays $birthsund $deathsArrays ist ein sehr guter Punkt, da das Sortieren von Blasen keine so schwere Aufgabe ist und es dennoch ermöglicht, einige Ecken zu schneiden:

<?php

$births = [1997, 1999, 2000];
$deaths = [2000, 2001, 2001];

function highestPopulationYear(array $births, array $deaths): Int {

    // sort takes time, but is neccesary for futher optimizations
    sort($births);
    sort($deaths);

    // first death year is a first year where population might decrase 
    // sorfar max population
    $currentYearComputing = $deaths[0];

    // year before first death has potential of having the biggest population
    $maxY = $currentYearComputing-1;

    // calculating population at the begining of the year of first death, start maxPopulation
    $population = $maxPop = count(array_splice($births, 0, array_search($deaths[0], $births)));

    // instead of every time empty checks: `while(!empty($deaths) || !empty($births))`
    // we can control a target time. It reserves a memory, but this slot is decreased
    // every iteration.
    $iterations = count($deaths) + count($births);

    while($iterations > 0) {
        while(current($births) === $currentYearComputing) {
            $population++;
            $iterations--;
            array_shift($births); // decreasing memory usage
        }

        while(current($deaths) === $currentYearComputing) {
            $population--;
            $iterations--;
            array_shift($deaths); // decreasing memory usage
        }

        if ($population > $maxPop) {
            $maxPop = $population;
            $maxY = $currentYearComputing;
        }

        // In $iterations we have a sum of birth/death events left. Assuming all 
        // are births, if this number added to currentPopulation will never exceed
        // current maxPoint, we can break the loop and save some time at cost of
        // some memory.
        if ($maxPop >= ($population+$iterations)) {
            break;
        }

        $currentYearComputing++;
    }

    return $maxY;
}

echo highestPopulationYear($births, $deaths);

Ich bin nicht wirklich daran interessiert, in das Big O- Ding einzutauchen, sondern habe es dir überlassen.

Wenn Sie currentYearComputingjede Schleife neu entdecken , können Sie Schleifen in ifAnweisungen ändern und mit nur einer Schleife verlassen.

    while($iterations > 0) {

        $changed = false;

        if(current($births) === $currentYearComputing) {
            // ...
            $changed = array_shift($births); // decreasing memory usage
        }

        if(current($deaths) === $currentYearComputing) {
            // ...
            $changed = array_shift($deaths); // decreasing memory usage
        }

        if ($changed === false) {
            $currentYearComputing++;
            continue;
        }

Ich fülle diese Lösung sehr bequem aus, die Komplexität Big O ist n + m

<?php
function getHighestPopulation($births, $deaths){
    $max = [];
    $currentMax = 0;
    $tmpArray = [];

    foreach($deaths as $key => $death){
        if(!isset($tmpArray[$death])){
            $tmpArray[$death] = 0;    
        }
        $tmpArray[$death]--;
    }
    foreach($births as $k => $birth){
        if(!isset($tmpArray[$birth])){
            $tmpArray[$birth] = 0;
        }
        $tmpArray[$birth]++;
        if($tmpArray[$birth] > $currentMax){
            $max = [$birth];
            $currentMax = $tmpArray[$birth];
        } else if ($tmpArray[$birth] == $currentMax) {
            $max[] = $birth;
        }
    }

    return [$currentMax, $max];
}

$births = [1997, 1997, 1997, 1998, 1999];
$deaths = [1998, 1999];

print_r (getHighestPopulation($births, $deaths));
?>

Einer der einfachsten und klarsten Ansätze für Ihr Problem.

$births = [1909, 1919, 1904, 1911, 1908, 1908, 1903, 1901, 1914, 1911, 1900, 1919, 1900, 1908, 1906];
$deaths = [1910, 1911, 1912, 1911, 1914, 1914, 1913, 1915, 1914, 1915];

/* for generating 1 million records

for($i=1;$i<=1000000;$i++) {
    $births[] = rand(1900, 2020);
    $deaths[] = rand(1900, 2020);
}
*/

function highestPopulationYear(Array $births, Array $deaths): Int {
    $start_time = microtime(true); 
    $population = array_count_values($births);
    $deaths = array_count_values($deaths);

    foreach ($deaths as $year => $death) {
        $population[$year] = ($population[$year] ?? 0) - $death;
    }
    ksort($population, SORT_NUMERIC);
    $cumulativeSum = $maxPopulation = $maxYear = 0;
    foreach ($population as $year => &$number) {
        $cumulativeSum += $number;
        if($maxPopulation < $cumulativeSum) {
            $maxPopulation = $cumulativeSum;
            $maxYear = $year;
        }
    }
    print " Execution time of function = ".((microtime(true) - $start_time)*1000)." milliseconds"; 
    return $maxYear;
}

print highestPopulationYear($births, $deaths);

Ausgabe :

1909

Komplexität :

O(m + log(n))