views 915 words

# Diffculty: Medium

## 378. Kth Smallest Element in a Sorted Matrix

Topic: Heap, Binary Search

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

return 13.

Note: You may assume k is always valid, 1 ≤ k ≤ n^2.

### Approach1

def kthSmallest(matrix: List[List[int]], k: int) -> int:
import heapq
# row = len(matrix)
# col = len(matrix[0])
# temp = [matrix[i][j] for i in range(col) for j in range(row)]
array = [y for x in matrix for y in x]
# print(temp)
# print(heapq.nsmallest(k,temp)) # [1, 5, 9, 10, 11, 12, 13, 13]
return heapq.nsmallest(k,temp)[-1]

### Approach2

def kthSmallest(matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
# 计算小于等于目标值的元素个数，根据递增规则，从右上角开始查找
def count_num(m, target):
i = 0
j = len(m) - 1
ans = 0
while i < len(m) and j >= 0:
if m[i][j] <= target:
ans += j + 1
i += 1
else:
j -= 1
return ans

#  思路：左上角元素最小，右下角元素最大，计算小于等于中间值的元素个数
left = matrix[0][0]
right = matrix[-1][-1]
# 二分法查找
while left < right:
mid = (left + right) >> 1
# print(' mid = ', mid)
count = count_num(matrix, mid)
# print('count = ', count)
if count < k:
left = mid + 1
else:
right = mid
return left

## 380. Insert Delete GetRandom O(1)

Topic: Stack, Design

Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

### Approach1

class RandomizedSet:

def __init__(self):
"""
"""
self.d = {}
self.l = []

def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.d:
return False
else:
self.d[val] = len(self.l)
self.l.append(val)
return True

def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val in self.d:
self.d[self.l[-1]] = self.d[val]
self.l[self.d.pop(val)] = self.l[-1]
self.l.pop()
return True
else:
return False

def getRandom(self) -> int:
"""
Get a random element from the set.
"""
return self.l[random.randint(0, len(self.l) - 1)]

# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

O(1)解法，组合使用哈希表和数组

## 384. Shuffle an Array

Topic:

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

## 395. Longest Substring with At Least K Repeating Characters

Topic:

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

## 454. 4Sum II

Topic:

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2^28 to 2^28 - 1 and the result is guaranteed to be at most 2^31 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

### Approach1

def 4sum(A,B,C,D):
res = defaultdict(int)
cnt = 0
for a in A:
for b in B:
res[a+b] += 1
for c in C:
for d in D:
cnt += res[-(c+d)]

return cnt