#️⃣ 배열, 우선순위 대기열, 빠른 선택
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]; };
설명:
- 배열 정렬: 정렬 방법을 사용하여 배열을 오름차순으로 정렬합니다.
- 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

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

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

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

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

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

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

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

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


핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

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

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

WebStorm Mac 버전
유용한 JavaScript 개발 도구

Dreamweaver Mac版
시각적 웹 개발 도구

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