LC 原题
报个new grad 店面
第一题 Given k sorted arrays of possibly different sizes, find m-th smallest value in the merged array.
Examples:
Input: m = 5
arr[][] = { {1, 3},
{2, 4, 6},
{0, 9, 10, 11}} ;
Output: 4
Explanation: The merged array would be {0 1 2 3 4 6 9 10 11}.
The 5-th smallest element in this merged array is 4.
Input: M = 2
arr[][] = { {1, 3, 20},
{2, 4, 6}} ;
Output: 2
Input: M = 6
arr[][] = { {1, 3, 20},
{2, 4, 6}} ;
Output: 20
我的python代码贴下吧
def m_smallest(lists, M: int) -> int:
if not lists:
return -1
min_heap = []
for i, l in enumerate(lists):
if l:
heapq.heappush(min_heap, (l[0], i, 1))
candidate = -1
while min_heap and M > 0:
min_val, i, j = heapq.heappop(min_heap)
if j < len(lists[i]):
heapq.heappush(min_heap, (lists[i][j], i, j + 1))
candidate, M = min_val, M - 1
return candidate
def _test(lists, M, expected):
actual = m_smallest(lists, M)
assert actual == expected, 'Wrong answer, expected: {}, actual: {}'.format(expected, actual)
print('Accepted')
if __name__ == '__main__':
lists, M = [[1, 3], [2, 4, 6], [0, 9, 10, 11]], 5
_test(lists, M, 4)
lists, M = [[1, 3, 20], [2, 4, 6]], 2
_test(lists, M, 2)
lists, M = [[1, 3, 20], [2, 4, 6]], 6
_test(lists, M, 20)
第二题 In a binary matrix (all elements are 0 and 1), every row is sorted in ascending order (0 to the left of 1).
Find the leftmost column index with a 1 in it.
Example 1:
Input:
[[0, 0, 0, 1],
[0, 0, 1, 1],
[0, 1, 1, 1],
[0, 0, 0, 0]]
Output: 1
Example 2:
Input:
[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
Output: -1
Expected solution better than O(r * c), after that better than O(r * log(c))
我的python代码贴下吧
def leftmost_index(grid) -> int:
if not grid or not grid[0]:
return -1
i, j = 0, len(grid[0]) - 1
result = -1
while i < len(grid) and j >= 0:
if j == 0:
break
if grid[i][j]:
result = j
j -= 1
else:
i += 1
return result
def _test(grid, expected):
actual = leftmost_index(grid)
assert actual == expected, 'Wrong answer'
print('Accepted')
if __name__ == '__main__':
grid = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 0]]
_test(grid, 1)
grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
_test(grid, -1)
grid = [[]]
_test(grid, -1)