백엔드 개발 PHP 문제 PHP에서 현재 숫자보다 작은 숫자의 수를 계산하는 방법

PHP에서 현재 숫자보다 작은 숫자의 수를 계산하는 방법

Jul 08, 2021 pm 03:57 PM
php

nums라는 배열이 주어졌습니다. 각 요소 nums[i]에 대해 배열에서 그보다 작은 모든 숫자의 수를 세어보세요. 오늘은 편집자가 현재 숫자보다 작은 숫자가 몇 개인지 계산하는 방법을 소개하겠습니다. 필요하시면 참고하시면 됩니다.

PHP에서 현재 숫자보다 작은 숫자의 수를 계산하는 방법

각 요소 nums[i]에 대해 배열에서 그보다 작은 모든 숫자의 수를 세어보세요.

즉, 각 nums[i]에 대해 j != i 및 nums[j] < nums[i] 와 같은 유효한 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 <= 5 00

  • 0 < = nums[i] <= 100

해결 방법 아이디어 1

배열의 각 숫자를 열거하고, 배열을 순회하며 현재 숫자보다 작은 숫자의 개수를 세어보세요.

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;
    }}
로그인 후 복사

해결 방법 질문 아이디어 2 - 주파수 배열 + 접두어 합

숫자의 값 범위는 [0,100][0,100]이므로 숫자의 횟수를 나타내는 빈도 배열 cnt[i]cnt[i]를 만드는 것을 고려할 수 있습니다. ii가 나타납니다. 즉, 숫자 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입니다.

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;
    }}
로그인 후 복사

추천 학습: php 비디오 튜토리얼

위 내용은 PHP에서 현재 숫자보다 작은 숫자의 수를 계산하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 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 Hentai를 무료로 생성하십시오.

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

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와 유사한 아키텍처를 기반으로 합니다. 모델, 뷰 및 컨트롤러 gu

PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 Dec 20, 2024 am 11:31 AM

VS Code라고도 알려진 Visual Studio Code는 모든 주요 운영 체제에서 사용할 수 있는 무료 소스 코드 편집기 또는 통합 개발 환경(IDE)입니다. 다양한 프로그래밍 언어에 대한 대규모 확장 모음을 통해 VS Code는

CakePHP 유효성 검사기 만들기 CakePHP 유효성 검사기 만들기 Sep 10, 2024 pm 05:26 PM

컨트롤러에 다음 두 줄을 추가하면 유효성 검사기를 만들 수 있습니다.

See all articles