Leetcode 719. 找出第 k 小的距离对

https://leetcode-cn.com/problems/find-k-th-smallest-pair-distance/description/

题意

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

思路

二分答案ans，问题转化为要求多少对值的差是比ans小的，如果这个数目超过k，则说明答案偏大，否则答案偏小。可以将数组排序，之后双指针扫描一遍数组即可

代码

class Solution: def calc(self, nums, x): sum = 0 last = 0 Len = len(nums) for i in range(0, Len, 1): while nums[i] - nums[last] > x: last += 1 sum += i - last return sum def smallestDistancePair(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ nums.sort() L, R = 0, 1000000 while L <= R: Mid = (L + R) // 2 if self.calc(nums, Mid) < k: L = Mid + 1 else: R = Mid - 1 return L

Leetcode 768. 最多能完成排序的块 II

https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/description/

题意

arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

思路

显然满足贪心性质，可以从 1 到 n 扫描数组，在能切割的地方就贪心的切割。问题变为了如何快速判定能否快速切割。进一步分析每一个切割点i，它必须要满足位置 1~i 包含的恰好是大小为 1~i 的数，那么创建一个辅助数组 Arr 为 arr 排序后的数组，i 从 1 到 n 遍历 arr 数组，设一个在 Arr 上面移动的指针 t ,每次指向前 i 个数中最大值在 Arr 中的位置，当 t = i 时就说明找到了一个可以切割的位置。

代码

class Solution: def maxChunksToSorted(self, arr): """ :type arr: List[int] :rtype: int """ Arr = sorted(arr) t = 0 ans = 0 Len = len(arr) for i in range(0, Len, 1): if (t < Len and arr[i] >= Arr[t]): while (Arr[t] < arr[i]): t += 1 t += 1 if (t == i + 1): ans += 1 return ans