Heim Backend-Entwicklung PHP-Problem So berechnen Sie in PHP, wie viele Zahlen kleiner als die aktuelle Zahl sind

So berechnen Sie in PHP, wie viele Zahlen kleiner als die aktuelle Zahl sind

Jul 08, 2021 pm 03:57 PM
php

Sie erhalten ein Array nums[i], bitte zählen Sie die Anzahl aller Zahlen im Array, die kleiner sind. Heute stellt der Herausgeber die Methode zur Berechnung vor, wie viele Zahlen kleiner als die aktuelle Zahl sind. Sie können bei Bedarf darauf zurückgreifen.

So berechnen Sie in PHP, wie viele Zahlen kleiner als die aktuelle Zahl sind

Ich gebe Ihnen ein Array nums Für jedes Element nums[i] zählen Sie bitte die Anzahl aller Zahlen, die kleiner als es im Array sind.

Mit anderen Worten, für jedes nums[i] müssen Sie die Anzahl der gültigen j berechnen, sodass j != i und nums[j] <

Gib die Antwort als Array zurück.

Beispiel 1:

输入:nums = [8,1,2,2,3]
输出:[4,0,1,1,3]
解释: 
对于 nums[0]=8 存在四个比它小的数字:(1,2,2 和 3)。 
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字:(1)。 
对于 nums[3]=2 存在一个比它小的数字:(1)。 
对于 nums[4]=3 存在三个比它小的数字:(1,2 和 2)。
Nach dem Login kopieren

Beispiel 2:

输入:nums = [6,5,4,8]
输出:[2,1,0,3]
Nach dem Login kopieren

Beispiel 3:

输入:nums = [7,7,7,7]
输出:[0,0,0,0]
Nach dem Login kopieren

Tipps:

  • 2 <=. nums .length <= 500

  • 0 < = nums[i] <= 100

Idee 1 zur Problemlösung

Zählen Sie jede Zahl im Array auf, durchlaufen Sie das Array und zählen Sie, wie viele Zahlen kleiner als die aktuelle Zahl sind

Code

class Solution {
    /** 
    * @param Integer[] $nums 
    * @return Integer[] 
    */
    function smallerNumbersThanCurrent($nums) {
        $count = count($nums);
        $result = array_fill(0, $count, 0);
        for ($i = 0; $i < $count; $i++) {
            for ($j = 0; $j < $count; $j++) {
                if ($nums[$j] < $nums[$i]) {
                    $result[$i]++;
                }
            }
        }
        return $result;
    }}
Nach dem Login kopieren

Lösung Frage Idee 2 – Häufigkeitsarray + Präfixsumme

Beachten Sie, dass der Wertebereich von Zahlen [0,100][0,100] beträgt. Sie können also erwägen, ein Häufigkeitsarray cnt[i]cnt[i] einzurichten, um die Häufigkeit darzustellen Die Zahl ii erscheint also. Für die Zahl ii lautet ihre Antwort: Das heißt, die Summe der Vorkommen kleinerer Zahlen berechnet direkt die cntcnt-Summe, die [0,i-1][0,i] durchlaufen muss −1], deren Berechnung immer noch lineare Zeit erfordert, aber wir bemerken, dass die Antwort eine Präfixsumme ist, sodass wir dann die Präfixsumme über das cntcnt-Array berechnen können. Dann ist die Antwort auf die Zahl ii cnt[i-1]cnt[i−1], und die zeitliche Komplexität der Berechnung der Antwort wird von O(n)O(n) auf O(1)O(1) reduziert.

Der letzte Algorithmusprozess besteht darin, die Array-Elemente zu durchlaufen, das cntcnt-Array zu aktualisieren, d. h. cnt[nums[i]]+=1, dann die Präfixsumme des cntcnt-Arrays zu berechnen und schließlich die Array-Elemente zu durchlaufen die entsprechende Zahl O(1)O (1) Holen Sie sich einfach die Antwort.

Die Zählsortierung ist eine spezielle Art der Bucket-Sortierung, die im Allgemeinen für Situationen geeignet ist, in denen die sortierte Datenlänge n viel größer ist als der Typ k. In dieser Frage ist beispielsweise k=101, n=500 oder sogar 5000.

Code

class Solution {
    /** 
    * @param Integer[] $nums 
    * @return Integer[] 
    */
    function smallerNumbersThanCurrent($nums) {
        $count = count($nums);
        $cnt = array_fill(0, 101, 0);    // 填充 0 的计数数组
        $result = array_fill(0, $count, 0);   // 填充 0 的结果数组
        // $nums 中出现的值和数量对应落到 $cnt 中
        foreach ($nums as $num) {
            $cnt[$num]++;
        }
        // $cnt 转化成 $i 的值是 sum($cnt[0], .. $cnt[$i - 1]) 新数组,即为小于 $i 的数据数量
        foreach (range(1, 100) as $i) {
            $cnt[$i] += $cnt[$i - 1];
        }
        // 结果数组中出现的 索引值 替换为 计数数组中的 数量
        foreach (range(0, $count - 1) as $i) {
            if ($nums[$i]) {
                $result[$i] = $cnt[$nums[$i] - 1];
            }
        }
        return $result;
    }}
Nach dem Login kopieren

Empfohlenes Lernen: php-Video-Tutorial

Das obige ist der detaillierte Inhalt vonSo berechnen Sie in PHP, wie viele Zahlen kleiner als die aktuelle Zahl sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
2 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Repo: Wie man Teamkollegen wiederbelebt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Abenteuer: Wie man riesige Samen bekommt
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

CakePHP-Projektkonfiguration CakePHP-Projektkonfiguration Sep 10, 2024 pm 05:25 PM

In diesem Kapitel werden wir die Umgebungsvariablen, die allgemeine Konfiguration, die Datenbankkonfiguration und die E-Mail-Konfiguration in CakePHP verstehen.

PHP 8.4 Installations- und Upgrade-Anleitung für Ubuntu und Debian PHP 8.4 Installations- und Upgrade-Anleitung für Ubuntu und Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 bringt mehrere neue Funktionen, Sicherheitsverbesserungen und Leistungsverbesserungen mit einer beträchtlichen Menge an veralteten und entfernten Funktionen. In dieser Anleitung wird erklärt, wie Sie PHP 8.4 installieren oder auf PHP 8.4 auf Ubuntu, Debian oder deren Derivaten aktualisieren. Obwohl es möglich ist, PHP aus dem Quellcode zu kompilieren, ist die Installation aus einem APT-Repository wie unten erläutert oft schneller und sicherer, da diese Repositorys in Zukunft die neuesten Fehlerbehebungen und Sicherheitsupdates bereitstellen.

CakePHP Datum und Uhrzeit CakePHP Datum und Uhrzeit Sep 10, 2024 pm 05:27 PM

Um in cakephp4 mit Datum und Uhrzeit zu arbeiten, verwenden wir die verfügbare FrozenTime-Klasse.

CakePHP-Datei hochladen CakePHP-Datei hochladen Sep 10, 2024 pm 05:27 PM

Um am Datei-Upload zu arbeiten, verwenden wir den Formular-Helfer. Hier ist ein Beispiel für den Datei-Upload.

CakePHP-Routing CakePHP-Routing Sep 10, 2024 pm 05:25 PM

In diesem Kapitel lernen wir die folgenden Themen im Zusammenhang mit dem Routing kennen.

Besprechen Sie CakePHP Besprechen Sie CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP ist ein Open-Source-Framework für PHP. Es soll die Entwicklung, Bereitstellung und Wartung von Anwendungen erheblich vereinfachen. CakePHP basiert auf einer MVC-ähnlichen Architektur, die sowohl leistungsstark als auch leicht zu verstehen ist. Modelle, Ansichten und Controller gu

So richten Sie Visual Studio-Code (VS-Code) für die PHP-Entwicklung ein So richten Sie Visual Studio-Code (VS-Code) für die PHP-Entwicklung ein Dec 20, 2024 am 11:31 AM

Visual Studio Code, auch bekannt als VS Code, ist ein kostenloser Quellcode-Editor – oder eine integrierte Entwicklungsumgebung (IDE) –, die für alle gängigen Betriebssysteme verfügbar ist. Mit einer großen Sammlung von Erweiterungen für viele Programmiersprachen kann VS Code c

CakePHP erstellt Validatoren CakePHP erstellt Validatoren Sep 10, 2024 pm 05:26 PM

Der Validator kann durch Hinzufügen der folgenden zwei Zeilen im Controller erstellt werden.

See all articles