찾다
웹 프론트엔드JS 튜토리얼배열에서 K번째로 큰 요소

Kth Largest Element in an Array

#️⃣ 배열, 우선순위 대기열, 빠른 선택

https://leetcode.com/problems/kth-largest-element-in-an-array/description

? 문제 이해

배열이 [8, 6, 12, 9, 3, 4]이고 k가 2인 경우 이 배열에서 두 번째로 큰 요소를 찾아야 합니다. 먼저 배열을 정렬합니다: [3, 4, 6, 8, 9, 12] 두 번째로 큰 요소이므로 출력은 9가 됩니다.

✅ 무차별 대입

var findKthLargest = function(nums, k) {
    // Sort the array in ascending order
    nums.sort((a, b) => a - b);

    // Return the kth largest element
    return nums[nums.length - k];
};

설명:

  1. 배열 정렬: 정렬 방법을 사용하여 배열을 오름차순으로 정렬합니다.
  2. k번째로 큰 요소 찾기: k번째로 큰 요소는 인덱스 nums.length - k의 요소에 액세스하여 찾습니다.

시간 복잡도:

  • 정렬: 배열 정렬의 시간 복잡도는 (O(nlog n))입니다. 여기서 (n)은 배열의 길이입니다.
  • 요소 액세스: 배열의 요소에 액세스하는 것은 O(1)입니다.

그러므로 전체 시간 복잡도는 O(n log n)입니다.

공간 복잡도:

  • 내부 정렬: 정렬 방법은 배열을 제자리에서 정렬하므로 정렬 작업의 공간 복잡도는 O(1)입니다.
  • 전체: 추가 데이터 구조를 사용하지 않으므로 전체 공간 복잡도는 O(1)입니다.

✅ 더 좋음

var findKthLargest = function(nums, k) {
        // Create a min-heap using a priority queue
        let minHeap = new MinPriorityQueue();

        // Add the first k elements to the heap
        for (let i = 0; i 



<h4>
  
  
  설명:
</h4>

<ol>
<li>
<strong>초기 배열</strong>: [2, 1, 6, 3, 5, 4]
</li>
<li>
<strong>k = 3</strong>: 세 번째로 큰 요소를 찾아야 합니다.</li>
</ol>

<h4>
  
  
  1단계: 최소 힙에 처음 k개 요소 추가
</h4>

  • 2를 추가한 후의 힙: [2]
  • 1을 추가한 후의 힙: [1, 2]
  • 6을 추가한 후의 힙: [1, 2, 6]

2단계: 나머지 요소 반복

  • 현재 요소 = 3

    • 비교 전 힙: [1, 2, 6]
    • 힙에서 가장 작은 요소(minHeap.front().element): 1
    • 비교: 3 > 1
    • Action: 1을 제거하고 3을 추가
    • 업데이트 후 힙: [2, 6, 3]
  • 현재 요소 = 5

    • 비교 전 힙: [2, 6, 3]
    • 힙에서 가장 작은 요소(minHeap.front().element): 2
    • 비교: 5 > 2
    • Action: 2를 제거하고 5를 추가
    • 업데이트 후 힙: [3, 6, 5]
  • 현재 요소 = 4

    • 비교 전 힙: [3, 6, 5]
    • 힙에서 가장 작은 요소(minHeap.front().element): 3
    • 비교: 4 > 3
    • Action: 3개 제거 및 4개 추가
    • 업데이트 후 힙: [4, 6, 5]

마지막 단계: 힙의 루트 반환

  • : [4, 6, 5]
  • 세 번째로 큰 요소: 4(힙의 루트)

시간 복잡도:

  • 힙 작업: 힙에서 요소를 삽입하고 제거하는 데는 O(log k) 시간이 걸립니다.
  • 전체: 배열의 n개 요소 각각에 대해 이러한 작업을 수행하므로 전체 시간 복잡도는 O(n log k)입니다.

공간 복잡도:

  • 힙 저장소: 힙은 최대 k개의 요소를 저장하므로 공간 복잡도는 O(k)입니다.

✅ 최고

참고: Leetcode가 빠른 선택을 제한하더라도 이 접근 방식은 대부분의 테스트 사례를 통과하므로 기억해야 합니다

//Quick Select Algo

function quickSelect(list, left, right, k)

   if left = right
      return list[left]

   Select a pivotIndex between left and right

   pivotIndex := partition(list, left, right, 
                                  pivotIndex)
   if k = pivotIndex
      return list[k]
   else if k 





<pre class="brush:php;toolbar:false">var findKthLargest = function(nums, k) {
    // Call the quickSelect function to find the kth largest element
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
};

function quickSelect(nums, low, high, index) {
    // If the low and high pointers are the same, return the element at low
    if (low === high) return nums[low];

    // Partition the array and get the pivot index
    let pivotIndex = partition(nums, low, high);

    // If the pivot index is the target index, return the element at pivot index
    if (pivotIndex === index) {
        return nums[pivotIndex];
    } else if (pivotIndex > index) {
        // If the pivot index is greater than the target index, search in the left partition
        return quickSelect(nums, low, pivotIndex - 1, index);
    } else {
        // If the pivot index is less than the target index, search in the right partition
        return quickSelect(nums, pivotIndex + 1, high, index);
    }
}

function partition(nums, low, high) {
    // Choose the pivot element
    let pivot = nums[high];
    let pointer = low;

    // Rearrange the elements based on the pivot
    for (let i = low; i 



<h4>
  
  
  Explanation:
</h4>

<ol>
<li>
<strong>Initial Array</strong>: [3, 2, 1, 5, 6, 4]
</li>
<li>
<strong>k = 2</strong>: We need to find the 2nd largest element.</li>
</ol>

<h4>
  
  
  Step 1: Partition the array
</h4>

  • Pivot element = 4
  • Array after partitioning: [3, 2, 1, 4, 6, 5]
  • Pivot index = 3

Step 2: Recursive Selection

  • Target index = 4 (since we need the 2nd largest element, which is the 4th index in 0-based indexing)
  • Pivot index (3) : Search in the right partition [6, 5]

Step 3: Partition the right partition

  • Pivot element = 5
  • Array after partitioning: [3, 2, 1, 4, 5, 6]
  • Pivot index = 4

Final Step: Return the element at the target index

  • Element at index 4: 5

Time Complexity:

  • Average Case: The average time complexity of Quickselect is O(n).
  • Worst Case: The worst-case time complexity is O(n^2), but this is rare with good pivot selection.

Space Complexity:

  • In-Place: The space complexity is O(1) because the algorithm works in place.

위 내용은 배열에서 K번째로 큰 요소의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
JavaScript 및 웹 : 핵심 기능 및 사용 사례JavaScript 및 웹 : 핵심 기능 및 사용 사례Apr 18, 2025 am 12:19 AM

웹 개발에서 JavaScript의 주요 용도에는 클라이언트 상호 작용, 양식 검증 및 비동기 통신이 포함됩니다. 1) DOM 운영을 통한 동적 컨텐츠 업데이트 및 사용자 상호 작용; 2) 사용자가 사용자 경험을 향상시키기 위해 데이터를 제출하기 전에 클라이언트 확인이 수행됩니다. 3) 서버와의 진실한 통신은 Ajax 기술을 통해 달성됩니다.

JavaScript 엔진 이해 : 구현 세부 사항JavaScript 엔진 이해 : 구현 세부 사항Apr 17, 2025 am 12:05 AM

보다 효율적인 코드를 작성하고 성능 병목 현상 및 최적화 전략을 이해하는 데 도움이되기 때문에 JavaScript 엔진이 내부적으로 작동하는 방식을 이해하는 것은 개발자에게 중요합니다. 1) 엔진의 워크 플로에는 구문 분석, 컴파일 및 실행; 2) 실행 프로세스 중에 엔진은 인라인 캐시 및 숨겨진 클래스와 같은 동적 최적화를 수행합니다. 3) 모범 사례에는 글로벌 변수를 피하고 루프 최적화, Const 및 Lets 사용 및 과도한 폐쇄 사용을 피하는 것이 포함됩니다.

Python vs. JavaScript : 학습 곡선 및 사용 편의성Python vs. JavaScript : 학습 곡선 및 사용 편의성Apr 16, 2025 am 12:12 AM

Python은 부드러운 학습 곡선과 간결한 구문으로 초보자에게 더 적합합니다. JavaScript는 가파른 학습 곡선과 유연한 구문으로 프론트 엔드 개발에 적합합니다. 1. Python Syntax는 직관적이며 데이터 과학 및 백엔드 개발에 적합합니다. 2. JavaScript는 유연하며 프론트 엔드 및 서버 측 프로그래밍에서 널리 사용됩니다.

Python vs. JavaScript : 커뮤니티, 라이브러리 및 리소스Python vs. JavaScript : 커뮤니티, 라이브러리 및 리소스Apr 15, 2025 am 12:16 AM

Python과 JavaScript는 커뮤니티, 라이브러리 및 리소스 측면에서 고유 한 장점과 단점이 있습니다. 1) Python 커뮤니티는 친절하고 초보자에게 적합하지만 프론트 엔드 개발 리소스는 JavaScript만큼 풍부하지 않습니다. 2) Python은 데이터 과학 및 기계 학습 라이브러리에서 강력하며 JavaScript는 프론트 엔드 개발 라이브러리 및 프레임 워크에서 더 좋습니다. 3) 둘 다 풍부한 학습 리소스를 가지고 있지만 Python은 공식 문서로 시작하는 데 적합하지만 JavaScript는 MDNWebDocs에서 더 좋습니다. 선택은 프로젝트 요구와 개인적인 이익을 기반으로해야합니다.

C/C에서 JavaScript까지 : 모든 것이 어떻게 작동하는지C/C에서 JavaScript까지 : 모든 것이 어떻게 작동하는지Apr 14, 2025 am 12:05 AM

C/C에서 JavaScript로 전환하려면 동적 타이핑, 쓰레기 수집 및 비동기 프로그래밍으로 적응해야합니다. 1) C/C는 수동 메모리 관리가 필요한 정적으로 입력 한 언어이며 JavaScript는 동적으로 입력하고 쓰레기 수집이 자동으로 처리됩니다. 2) C/C를 기계 코드로 컴파일 해야하는 반면 JavaScript는 해석 된 언어입니다. 3) JavaScript는 폐쇄, 프로토 타입 체인 및 약속과 같은 개념을 소개하여 유연성과 비동기 프로그래밍 기능을 향상시킵니다.

JavaScript 엔진 : 구현 비교JavaScript 엔진 : 구현 비교Apr 13, 2025 am 12:05 AM

각각의 엔진의 구현 원리 및 최적화 전략이 다르기 때문에 JavaScript 엔진은 JavaScript 코드를 구문 분석하고 실행할 때 다른 영향을 미칩니다. 1. 어휘 분석 : 소스 코드를 어휘 단위로 변환합니다. 2. 문법 분석 : 추상 구문 트리를 생성합니다. 3. 최적화 및 컴파일 : JIT 컴파일러를 통해 기계 코드를 생성합니다. 4. 실행 : 기계 코드를 실행하십시오. V8 엔진은 즉각적인 컴파일 및 숨겨진 클래스를 통해 최적화하여 Spidermonkey는 유형 추론 시스템을 사용하여 동일한 코드에서 성능이 다른 성능을 제공합니다.

브라우저 너머 : 실제 세계의 JavaScript브라우저 너머 : 실제 세계의 JavaScriptApr 12, 2025 am 12:06 AM

실제 세계에서 JavaScript의 응용 프로그램에는 서버 측 프로그래밍, 모바일 애플리케이션 개발 및 사물 인터넷 제어가 포함됩니다. 1. 서버 측 프로그래밍은 Node.js를 통해 실현되며 동시 요청 처리에 적합합니다. 2. 모바일 애플리케이션 개발은 재교육을 통해 수행되며 크로스 플랫폼 배포를 지원합니다. 3. Johnny-Five 라이브러리를 통한 IoT 장치 제어에 사용되며 하드웨어 상호 작용에 적합합니다.

Next.js (백엔드 통합)로 멀티 테넌트 SAAS 애플리케이션 구축Next.js (백엔드 통합)로 멀티 테넌트 SAAS 애플리케이션 구축Apr 11, 2025 am 08:23 AM

일상적인 기술 도구를 사용하여 기능적 다중 테넌트 SaaS 응용 프로그램 (Edtech 앱)을 구축했으며 동일한 작업을 수행 할 수 있습니다. 먼저, 다중 테넌트 SaaS 응용 프로그램은 무엇입니까? 멀티 테넌트 SAAS 응용 프로그램은 노래에서 여러 고객에게 서비스를 제공 할 수 있습니다.

See all articles

핫 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를 무료로 생성하십시오.

뜨거운 도구

MinGW - Windows용 미니멀리스트 GNU

MinGW - Windows용 미니멀리스트 GNU

이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.

메모장++7.3.1

메모장++7.3.1

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

WebStorm Mac 버전

WebStorm Mac 버전

유용한 JavaScript 개발 도구

Dreamweaver Mac版

Dreamweaver Mac版

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)