ホームページ バックエンド開発 PHPの問題 PHPで現在の数値より小さい数値の数を計算する方法

PHPで現在の数値より小さい数値の数を計算する方法

Jul 08, 2021 pm 03:57 PM
php

配列 nums を与えます。各要素 nums[i] について、配列内のそれより小さいすべての数値の数を数えてください。どうすればよいですか?今回は、現在の数字より何個小さいかを計算する方法を編集者が紹介しますので、必要な場合は参考にしてください。

PHPで現在の数値より小さい数値の数を計算する方法

配列 nums が与えられた場合、各要素 nums[i] について、配列内のそれより小さいすべての数値の数を数えてください。

言い換えると、 nums[i] ごとに、 j != i および nums[j]

答えを配列として返します。

例 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)。
ログイン後にコピー

例 2:

输入:nums = [6,5,4,8]
输出:[2,1,0,3]
ログイン後にコピー

例 3:

输入:nums = [7,7,7,7]
输出:[0,0,0,0]
ログイン後にコピー

ヒント:

  • 2 <= nums.length <= 500

  • ##0 <= nums[i] < ; = 100

解決策のアイデア 1

配列内の各数値を列挙し、配列を走査して、現在の数値より小さい数値がいくつあるかを数えます。 Just

コード

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;
    }}
ログイン後にコピー

ソリューションアイデア 2 - 周波数配列プレフィックスと

数値の値の範囲が [0,100][0,100 ] であることに注意してください。したがって、数値 ii が出現する回数を表す頻度配列 cnt[i]cnt[i] を確立することを検討できます。次に、数値 ii の答え、つまり、以下の数値の出現回数の合計です。 [0,i-1][0,i−1] の cntcnt 合計をたどるには、依然として計算に線形時間が必要ですが、答えはプレフィックスの合計であることに注意してください。したがって、プレフィックスを計算できます。 cntcnt 配列の合計。この場合、数値 ii の答えは cnt[i-1]cnt[i-1] となり、答えを計算する時間計算量は O(n)O(n) から O(1)O(1) に軽減されます。

最終的な全体のアルゴリズム プロセスは次のとおりです。配列要素を走査し、cntcnt 配列を更新します (つまり、cnt[nums[i]] = 1)。その後、cntcnt 配列のプレフィックスの合計を計算し、最後に配列の要素に対応する数値 O( 1)O(1) を求めれば答えが得られます。

カウンティング ソートは特別な種類のバケット ソートであり、通常、ソートされたデータの長さ n がタイプ k よりもはるかに大きい状況に適しています。たとえば、この質問では k=101、n=500、さらには 5000 です。

コード

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;
    }}
ログイン後にコピー
推奨学習:

phpビデオチュートリアル

以上がPHPで現在の数値より小さい数値の数を計算する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

CakePHP プロジェクトの構成 CakePHP プロジェクトの構成 Sep 10, 2024 pm 05:25 PM

この章では、CakePHP の環境変数、一般設定、データベース設定、電子メール設定について理解します。

Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Dec 24, 2024 pm 04:42 PM

PHP 8.4 では、いくつかの新機能、セキュリティの改善、パフォーマンスの改善が行われ、かなりの量の機能の非推奨と削除が行われています。 このガイドでは、Ubuntu、Debian、またはその派生版に PHP 8.4 をインストールする方法、または PHP 8.4 にアップグレードする方法について説明します。

CakePHP の日付と時刻 CakePHP の日付と時刻 Sep 10, 2024 pm 05:27 PM

Cakephp4 で日付と時刻を操作するには、利用可能な FrozenTime クラスを利用します。

CakePHP ファイルのアップロード CakePHP ファイルのアップロード Sep 10, 2024 pm 05:27 PM

ファイルのアップロードを行うには、フォーム ヘルパーを使用します。ここではファイルアップロードの例を示します。

CakePHP ルーティング CakePHP ルーティング Sep 10, 2024 pm 05:25 PM

この章では、ルーティングに関連する次のトピックを学習します。

CakePHP について話し合う CakePHP について話し合う Sep 10, 2024 pm 05:28 PM

CakePHP は、PHP 用のオープンソース フレームワークです。これは、アプリケーションの開発、展開、保守をより簡単にすることを目的としています。 CakePHP は、強力かつ理解しやすい MVC のようなアーキテクチャに基づいています。モデル、ビュー、コントローラー

PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 Dec 20, 2024 am 11:31 AM

Visual Studio Code (VS Code とも呼ばれる) は、すべての主要なオペレーティング システムで利用できる無料のソース コード エディター (統合開発環境 (IDE)) です。 多くのプログラミング言語の拡張機能の大規模なコレクションを備えた VS Code は、

CakePHP バリデータの作成 CakePHP バリデータの作成 Sep 10, 2024 pm 05:26 PM

Validator は、コントローラーに次の 2 行を追加することで作成できます。

See all articles