LeetCode day31

5 minutes read
LeetCode
#LeetCode
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

二分查找法，根据题目可得左上角元素最小，右下角元素最大，计算中间值。然后计算小于等于目标值的元素个数，根据递增规则，从右上角开始查找，类似于题目“二维数组的查找”

时间复杂度：O(nlogk) ，k=最大值-最小值

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):
        """
        Initialize your data structure here.
        """
        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)解法，组合使用哈希表和数组

插入时：用哈希表来判断是否已存在O(1)，数组末尾增加一个元素O(1)，哈希表记录｛值：索引｝O(1)

删除时：用哈希表来定位O(1)，把数组最后一个元素取下来顶替被删除元素位置O(1)，更新哈希表O(1)

取随机数时：随机从数组里面挑一个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();

Approach1

Approach2

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.

Approach1

Approach2

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

Approach2