Leetcode Problem: Kth Largest Element in an Array
- Heap Solution
Java
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < k; i++) {
minHeap.offer(nums[i]);
}
for (int i = k; i < nums.length; i++) {
if (nums[i] > minHeap.peek()) {
minHeap.poll();
minHeap.offer(nums[i]);
}
}
return minHeap.peek();
}Python
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, num)
return heap[0]- Quick-Selection solution
Java
public int findKthLargest(int[] nums, int k) {
int left = 0, right = nums.length - 1;
Random rand = new Random();
while (true) {
int pivot_index = left + rand.nextInt(right - left + 1);
int new_pivot_index = partition(nums, left, right, pivot_index);
if (new_pivot_index == nums.length - k) {
return nums[new_pivot_index];
} else if (new_pivot_index > nums.length - k) {
right = new_pivot_index - 1;
} else {
left = new_pivot_index + 1;
}
}
}
private int partition(int[] nums, int left, int right, int pivot_index) {
int pivot = nums[pivot_index];
swap(nums, pivot_index, right);
int stored_index = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivot) {
swap(nums, i, stored_index);
stored_index++;
}
}
swap(nums, right, stored_index);
return stored_index;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}Python
def findKthLargest(self, nums, k):
left, right = 0, len(nums) - 1
while True:
pivot_index = random.randint(left, right)
new_pivot_index = self.partition(nums, left, right, pivot_index)
if new_pivot_index == len(nums) - k:
return nums[new_pivot_index]
elif new_pivot_index > len(nums) - k:
right = new_pivot_index - 1
else:
left = new_pivot_index + 1
def partition(self, nums, left, right, pivot_index):
pivot = nums[pivot_index]
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
stored_index = left
for i in range(left, right):
if nums[i] < pivot:
nums[i], nums[stored_index] = nums[stored_index], nums[i]
stored_index += 1
nums[right], nums[stored_index] = nums[stored_index], nums[right]
return stored_indexLeetcode problem: Find All Anagrams in a String
Java
public List<Integer> findAnagrams(String s, String p) {
int[] pcount = new int[26];
int[] scount = new int[26];
List<Integer> result = new ArrayList<>();
for (char c : p.toCharArray()) {
pcount[c - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
scount[s.charAt(i) - 'a']++;
if (i >= p.length()) {
scount[s.charAt(i - p.length()) - 'a']--;
}
if (Arrays.equals(pcount, scount)) {
result.add(i - p.length() + 1);
}
}
return result;
}Python
- List
def findAnagrams(self, s, p):
if len(s) < len(p):
return []
p_count = [0] * 26
s_count = [0] * 26
for char in p:
p_count[ord(char) - ord('a')] += 1
result = []
for i in range(len(s)):
s_count[ord(s[i]) - ord('a')] += 1
if i >= len(p):
s_count[ord(s[i - len(p)]) - ord('a')] -= 1
if s_count == p_count:
result.append(i - len(p) + 1)
return result- Dict
def findAnagrams(self, s, p):
if len(s) < len(p):
return []
p_count = {}
for char in p:
p_count[char] = p_count.get(char, 0) + 1
result = []
s_count = {}
p_len = len(p)
for i in range(len(s)):
char_in = s[i]
s_count[char_in] = s_count.get(char_in, 0) + 1
if i >= p_len:
char_out = s[i - p_len]
s_count[char_out] -= 1
if s_count[char_out] == 0:
del s_count[char_out]
if i >= p_len - 1:
if s_count == p_count:
result.append(i - p_len + 1)
return resultProblem 3: Radix Sort Leetcode problem: Sort an array
- Positive only solution
Java
private void countingSortBits(int[] arr, int n, int bitShift, int numBits) {
int base = 1 << numBits;
int mask = base - 1;
int[] count = new int[base];
int[] output = new int[n];
for (int i = 0; i < n; i++) {
int digit = (arr[i] >> bitShift) & mask;
count[digit]++;
}
for (int i = 1; i < base; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] >> bitShift) & mask;
int outputIndex = count[digit] - 1;
output[outputIndex] = arr[i];
count[digit]--;
}
System.arraycopy(output, 0, arr, 0, n);
}
public int[] sortArray(int[] nums) {
int n = nums.length;
if (n <= 1) {
return nums;
}
// assumes max value is < 2^20
final int MAX_BITS = 20;
int bitsPerPass = Math.max(1, (int) (Math.log(n) / Math.log(2)));
int bitShift = 0;
while (bitShift < MAX_BITS) {
countingSortBits(nums, n, bitShift, bitsPerPass);
bitShift += bitsPerPass;
}
return nums;
}Python
def counting_sort_bits(self, arr, n, bit_shift, num_bits):
base = 1 << num_bits
mask = base - 1
count = [0] * base
output = [0] * n
for i in range(n):
digit = (arr[i] >> bit_shift) & mask
count[digit] += 1
for i in range(1, base):
count[i] += count[i - 1]
for i in range(n - 1, -1, -1):
digit = (arr[i] >> bit_shift) & mask
output_index = count[digit] - 1
output[output_index] = arr[i]
count[digit] -= 1
for i in range(n):
arr[i] = output[i]
def sortArray(self, nums: List[int]) -> List[int]:
n = len( nums)
if n <= 1:
return nums
# Max value is fixed at 10^6 - 1, which needs 20 bits.
MAX_BITS = 20
bits_per_pass = max(1, int(math.log2(n)))
bit_shift = 0
while bit_shift < MAX_BITS:
self.counting_sort_bits(nums, n, bit_shift, bits_per_pass)
bit_shift += bits_per_pass
return nums
- Allow Negative
Python
def counting_sort_digits(self, arr: List[int], n: int, exp: int):
BASE = 10
count = [0] * BASE
output = [0] * n
for i in range(n):
digit = (arr[i] // exp) % BASE
count[digit] += 1
for i in range(1, BASE):
count[i] += count[i - 1]
for i in range(n - 1, -1, -1):
digit = (arr[i] // exp) % BASE
output_index = count[digit] - 1
output[output_index] = arr[i]
count[digit] -= 1
for i in range(n):
arr[i] = output[i]
def sortArray(self, nums: List[int]) -> List[int]:
n = len(nums)
if n <= 1:
return nums
min_val = min(nums)
offset = 0
if min_val < 0:
offset = -min_val
for i in range(n):
nums[i] += offset
max_val = max(nums) if n > 0 else 0
exp = 1
while max_val // exp > 0:
self.counting_sort_digits(nums, n, exp)
exp *= 10
if offset > 0:
for i in range(n):
nums[i] -= offset
return nums