Guide Tri · 5/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
Most sorting problems are not "implement a sort" but "sort first, then the rest is easy". The four problems below practice sort-then-scan, multi-key ordering, custom comparators and reusing the merge step. Try each one before reading the solution.
Room bookings are given as (start, end) pairs of integers in no particular order. Merge bookings that overlap or touch, and return the periods when the room is actually in use, ordered by start time. For [(9, 11), (13, 15), (10, 12), (15, 16)] the answer is [[9, 12], [13, 16]].
Approach: after sorting by start time, a booking can only overlap the last merged period. Scan in order; if the current start is at most the last end, extend that end, otherwise open a new period. Sorting costs O(n log n) and the scan O(n).
def merge_bookings(bookings):
result = []
for start, end in sorted(bookings):
if result and start <= result[-1][1]:
result[-1][1] = max(result[-1][1], end)
else:
result.append([start, end])
return result
print(merge_bookings([(9, 11), (13, 15), (10, 12), (15, 16)])) # [[9, 12], [13, 16]]Each contestant has (name, score, seconds). Rank by score descending, then by time ascending, then by name alphabetically.
Approach: one tuple key expresses all three criteria, and negating the numeric score turns it into descending order. If a criterion that cannot be negated (such as a string) must be descending, run several stable sorts from the least to the most significant criterion. Python's reverse=True preserves stability too.
players = [("lee", 90, 300), ("kim", 95, 410), ("park", 90, 280), ("choi", 90, 300)]
ranked = sorted(players, key=lambda p: (-p[1], p[2], p[0]))
print([p[0] for p in ranked]) # ['kim', 'park', 'choi', 'lee']
# The same result with repeated stable sorts, least significant key first
step = sorted(players, key=lambda p: p[0])
step = sorted(step, key=lambda p: p[2])
step = sorted(step, key=lambda p: p[1], reverse=True)
print([p[0] for p in step]) # ['kim', 'park', 'choi', 'lee']Given non-negative integers, arrange them so that their concatenation is the largest possible number, and return it as a string. For [3, 30, 34, 5, 9] the answer is "9534330". If all values are zero, return "0".
Approach: sorting numerically or lexicographically fails on pairs like 3 and 30. Instead compare two strings a and b by whichever of a + b and b + a is larger. This comparison is transitive, so it is a valid sort order. Strip leading zeros so that becomes .
"000""0"from functools import cmp_to_key
def largest_number(nums):
words = [str(n) for n in nums]
def compare(a, b):
if a + b > b + a:
return -1 # a goes first
if a + b < b + a:
return 1
return 0
words.sort(key=cmp_to_key(compare))
return "".join(words).lstrip("0") or "0"
print(largest_number([3, 30, 34, 5, 9])) # 9534330
print(largest_number([0, 0])) # 0Count the pairs i < j with a[i] > a[j] (inversions) in an integer array of up to 200,000 elements. For example, [3, 1, 2] has two: (3, 1) and (3, 2).
Approach: checking every pair is O(n²), far too slow. During the merge step of merge sort, when right[j] is taken, the len(left) - i elements still waiting on the left are all larger and originally came earlier, so each forms an inversion. Adding these counts yields the answer in O(n log n) while sorting.
def count_inversions(a):
def solve(items):
if len(items) <= 1:
return items, 0
mid = len(items) // 2
left, x = solve(items[:mid])
right, y = solve(items[mid:])
merged, i, j, cross = [], 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
cross += len(left) - i
merged += left[i:] + right[j:]
return merged, x + y + cross
return solve(list(a))[1]
print(count_inversions([3, 1, 2])) # 2
print(count_inversions([5, 4, 3, 2, 1])) # 10Equal values are not inversions, so the left element must be taken on ties (<=). Using < would count equal pairs by mistake.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.