Kth Largest Element in an Array (in Python) / Quick select
Problem Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.Example 1:Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2:Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4Note: You may assume k is always valid, 1 ≤ k ≤ array's length. Solution 123456789101112131415161718192021222324252627282930313233343536373839..
회전된 배열에서의 검색 (이진 탐색)
n개의 정수로 구성된 정렬 상태의 배열을 임의의 횟수만큼 회전시켜 얻은 배열이 입력으로 주어진다고 하자. 이 배열에서 특정한 원소를 찾는 코드를 작성하라. 회전시키기 전, 원래 배열은 오름차순으로 정렬되어있었다고 가정한다. 예제) 입력: {15,16,19,20,25,1,3,4,5,7,10,14} 출력: 8 (배열에서 5가 위치한 인덱스) 고전적인 이진 탐색은 어떤 값 x가 왼쪽에 있는지 아니면 오른쪽에 있는지 판단하기 위해 x를 배열의 중간 원소와 비교한다. 하지만 이 문제는, 배열이 회전된 상태라서 까다롭다. 가령, 다음의 두 배열을 살펴보자. 배열1 : [10, 15, 20, 0, 5] 배열2: [50, 5, 20, 30, 40] 이 두 배열이 모두 20이 중간에 있지만, 5는 왼쪽에 있을 수도 있고..
Contains Duplicate3 (in Python)
ProblemGiven an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.Example 1:Input: nums = [1,2,3,1], k = 3, t = 0 Output: true Example 2:Input: nums = [1,0,1,1], k = 1, t = 2 Output: true Example 3:Input: nums = [1,5,9,1,5,9], k..