技术图文：排序技术在求解算法题中的应用

背景

前段时间，在知识星球立了一个Flag，这是总结Leetcode刷题的第五篇图文。

理论部分

C# 中的排序

对集合类的排序，我们通常使用位于 System.Core 程序集，System.Linq命名空间下，Enumerable静态类中的扩展方法。

public static class Enumerable
{public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);
}

该OrderBy是对IEnumerable<T>类型的扩展，而IEnumerable<T>是整个 LINQ 的基础。C# 大部分数据结构都实现了IEnumerable<T>。

有关扩展方法参见图文：

• 技术图文：C# 语言中的扩展方法

Python 中的排序

对列表的排序通常有两种方法，第一种使用list本身的sort方法，第二种使用 Python 的内置方法sorted。

list.sort( key=None, reverse=False) 对原列表进行排序。

• key – 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
• reverse – 排序规则，reverse = True 降序， reverse = False 升序（默认）。
• 该方法没有返回值，但是会对列表的对象进行排序。

Sample01：

list1 = [123, 456, 789, 213]
list1.sort()
print(list1)  # [123, 213, 456, 789]list1.sort(reverse=True)
print(list1)  # [789, 456, 213, 123]

Sample02：

# 获取列表的第二个元素
def takeSecond(elem):return elem[1]r = [(2, 2), (3, 4), (4, 1), (1, 3)]
r.sort(key=takeSecond)
print(r)# [(4, 1), (2, 2), (1, 3), (3, 4)]

sorted(iterable, key=None, reverse=False) 对所有可迭代的对象进行排序操作。

• iterable – 可迭代对象。
• key – 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
• reverse – 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。
• 返回重新排序的列表。

Sample01：

numbers = [-8, 99, 3, 7, 83]
print(sorted(numbers))  # [-8, 3, 7, 83, 99]
print(sorted(numbers, reverse=True))  # [99, 83, 7, 3, -8]

Sample02：

array = [{"age": 20, "name": "a"}, {"age": 25, "name": "b"}, {"age": 10, "name": "c"}]
array = sorted(array, key=lambda x: x["age"])
print(array)# [{'age': 10, 'name': 'c'}, {'age': 20, 'name': 'a'}, {'age': 25, 'name': 'b'}]

应用部分

题目1：求众数

• 题号：169
• 难度：简单
• https://leetcode-cn.com/problems/majority-element/

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

思路：利用排序的方法

C# 语言

• 状态：通过
• 44 / 44 个通过测试用例
• 执行用时：192 ms

public class Solution 
{public int MajorityElement(int[] nums) {nums = nums.OrderBy(a => a).ToArray();return nums[nums.Length / 2];}
}

Python 语言

• 执行结果：通过
• 执行用时：48 ms, 在所有 Python3 提交中击败了 82.08% 的用户
• 内存消耗：15.2 MB, 在所有 Python3 提交中击败了 6.90% 的用户

class Solution:def majorityElement(self, nums: List[int]) -> int:nums.sort()return nums[len(nums) // 2]

题目2：数组中的第K个最大元素

• 题号：215
• 难度：中等
• https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

思路：利用排序的方法

C# 语言

• 状态：通过
• 32 / 32 个通过测试用例
• 执行用时: 152 ms, 在所有 C# 提交中击败了 76.47% 的用户
• 内存消耗: 24.6 MB, 在所有 C# 提交中击败了 5.55% 的用户

public class Solution
{public int FindKthLargest(int[] nums, int k){nums = nums.OrderBy(a => a).ToArray();return nums[nums.Length - k];}
}

Python 语言

• 执行结果：通过
• 执行用时：40 ms, 在所有 Python3 提交中击败了 92.64% 的用户
• 内存消耗：14.4 MB, 在所有 Python3 提交中击败了 15.79% 的用户

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:nums.sort()return nums[len(nums) - k]

题目3：350. 两个数组的交集 II

• 题号：350
• 难度：简单
• https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

• 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
• 我们可以不考虑输出结果的顺序。

进阶:

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果nums1的大小比nums2小很多，哪种方法更优？
• 如果nums2的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

思路：利用 排序 + 双索引 的方法

C# 语言

• 执行结果：通过
• 执行用时：320 ms, 在所有 C# 提交中击败了 23.03% 的用户
• 内存消耗：31.2 MB, 在所有 C# 提交中击败了 100.00% 的用户

public class Solution 
{public int[] Intersect(int[] nums1, int[] nums2){            nums1 = nums1.OrderBy(a => a).ToArray();nums2 = nums2.OrderBy(a => a).ToArray();List<int> result = new List<int>();int i = 0, j = 0;while (i < nums1.Length && j < nums2.Length){if (nums1[i] < nums2[j]){i++;}else if (nums1[i] > nums2[j]){j++;}else{result.Add(nums1[i]);i++;j++;}}return result.ToArray();}
}

Python 语言

• 执行结果：通过
• 执行用时：64 ms, 在所有 Python3 提交中击败了 62.00% 的用户
• 内存消耗：13.7 MB, 在所有 Python3 提交中击败了 12.50% 的用户

class Solution:def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:nums1.sort()nums2.sort()result = []i, j = 0, 0while i < len(nums1) and j < len(nums2):if nums1[i] < nums2[j]:i += 1elif nums1[i] > nums2[j]:j += 1else:result.append(nums1[i])i += 1j += 1return result

题目4：最接近的三数之和

• 题号：16
• 难度：中等
• https://leetcode-cn.com/problems/3sum-closest/

给定一个包括n个整数的数组nums和一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例 :

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

思路：利用 排序 + 三索引 的方法

C# 实现

• 状态：通过
• 125 / 125 个通过测试用例
• 执行用时: 132 ms, 在所有 C# 提交中击败了 100.00% 的用户
• 内存消耗: 24 MB, 在所有 C# 提交中击败了 5.55% 的用户

public class Solution 
{public int ThreeSumClosest(int[] nums, int target) {nums = nums.OrderBy(a => a).ToArray();int result = nums[0] + nums[1] + nums[2];for (int i = 0; i < nums.Length - 2; i++){int start = i + 1, end = nums.Length - 1;while (start < end){int sum = nums[start] + nums[end] + nums[i];if (Math.Abs(target - sum) < Math.Abs(target - result))result = sum;if (sum > target)end--;else if (sum < target)start++;elsereturn result;}}return result;        }
}

Pyhton 实现

• 执行结果：通过
• 执行用时：124 ms, 在所有 Python3 提交中击败了 72.19% 的用户
• 内存消耗：13.2 MB, 在所有 Python3 提交中击败了 22.06% 的用户

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:nums = sorted(nums)result = nums[0] + nums[1] + nums[2]for i in range(0, len(nums) - 2):start = i + 1end = len(nums) - 1while start < end:sum = nums[start] + nums[end] + nums[i]if abs(target - sum) < abs(target - result):result = sumif sum > target:end -= 1elif sum < target:start += 1else:return resultreturn result

题目5：三数之和

• 题号：15
• 难度：中等
• https://leetcode-cn.com/problems/3sum/

给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a + b + c = 0？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：
[[-1, 0, 1],[-1, -1, 2]
]

思路：利用 排序 + 三索引 的方法

为了避免三次循环，提升执行效率。首先，对nums进行排序。然后，固定3个索引i,l(left),r(right)，i进行最外层循环，l指向nums[i]之后数组的最小值，r指向nums[i]之后数组的最大值。模仿快速排序的思路，如果nums[i] > 0就不需要继续计算了，否则计算nums[i] + nums[l] + nums[r]是否等于零并进行相应的处理。如果大于零，向l方向移动r指针，如果小于零，向r方向移动l索引，如果等于零，则加入到存储最后结果的result链表中。当然，题目中要求这个三元组不可重复，所以在进行的过程中加入去重就好。

C# 实现

• 执行结果：通过
• 执行用时：348 ms, 在所有 C# 提交中击败了 99.54% 的用户
• 内存消耗：35.8 MB, 在所有 C# 提交中击败了 6.63% 的用户

public class Solution 
{public IList<IList<int>> ThreeSum(int[] nums) {IList<IList<int>> result = new List<IList<int>>();nums = nums.OrderBy(a => a).ToArray();int len = nums.Length;for (int i = 0; i < len - 2; i++){if (nums[i] > 0) break; // 如果最小的数字大于0, 后面的操作已经没有意义if (i > 0 && nums[i - 1] == nums[i])continue; // 跳过三元组中第一个元素的重复数据int l = i + 1;int r = len - 1;while (l < r){int sum = nums[i] + nums[l] + nums[r];if (sum < 0){l++;}else if (sum > 0){r--;}else{result.Add(new List<int>() {nums[i], nums[l], nums[r]});// 跳过三元组中第二个元素的重复数据while (l < r && nums[l] == nums[l + 1]) {l++;}// 跳过三元组中第三个元素的重复数据while (l < r && nums[r - 1] == nums[r]) {r--;}l++;r--;}}}return result;    }
}

Python 实现

• 执行结果：通过
• 执行用时：660 ms, 在所有 Python3 提交中击败了 95.64% 的用户
• 内存消耗：16.1 MB, 在所有 Python3 提交中击败了 75.29% 的用户

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums = sorted(nums)result = []for i in range(0, len(nums) - 2):# 如果最小的数字大于0, 后面的操作已经没有意义if nums[i] > 0:break# 跳过三元组中第一个元素的重复数据if i > 0 and nums[i-1] == nums[i]:continue# 限制nums[i]是三元组中最小的元素l = i + 1r = len(nums) - 1            while l < r:sum = nums[i] + nums[l] + nums[r]if sum < 0:l += 1elif sum > 0:r -= 1else:result.append([nums[i], nums[l], nums[r]])# 跳过三元组中第二个元素的重复数据while l < r and nums[l] == nums[l+1]:l += 1# 跳过三元组中第三个元素的重复数据while l < r and nums[r] == nums[r-1]:r -= 1                    l += 1r -= 1return result

总结

本篇图文首先介绍了 C# 和 Python 语言对集合元素的排序方法，我们通过五道Leetcode题演示了排序技术在求解算法题目中的应用，希望能够对大家有所帮助。目前 Flag 计划已经执行 100%，全部完成啦！等下次算法刻意练训练营之后，再来总结新的知识点。今天就到这里吧！See You！

当前活动

我是 终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：