【数据结构与算法】之排序系列-20240201
- 一、88. 合并两个有序数组
- 二、169. 多数元素
- 三、217. 存在重复元素
- 四、242. 有效的字母异位词
- 五、268. 丢失的数字
- 六、349. 两个数组的交集
- 七、350. 两个数组的交集 II
一、88. 合并两个有序数组
简单
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
class Solution88: def func(self, nums1, m, nums2, n): if n != 0: if m == 0: nums1[:] = nums2[:] else: p = 0 q = 0 result = [0] * (m + n) for i in range(m + n): if nums1[p] > nums2[q]: result[i] = nums2[q] q += 1 else: result[i] = nums1[p] p += 1 if p == m and q != n: result[i + 1:] = nums2[q:] elif p != m and q == n: result[i + 1:] = nums1[p:m] if p == m or q == n: break nums1[:] = result[:] return nums1 r = Solution88() nums1 = [1, 2, 3, 0, 0, 0] nums2 = [2, 5, 6] m = 3 n = 3 print(r.func(nums1, m, nums2, n))二、169. 多数元素
简单
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
def func169(nums): nums.sort() return nums[len(nums) // 2] nums = [3, 2, 3] print(func169(nums))三、217. 存在重复元素
简单
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]
输出：true
示例 2：
输入：nums = [1,2,3,4]
输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
def func217(nums): return len(nums) != len(set(nums)) nums = [1, 2, 3, 1] print(func217(nums))四、242. 有效的字母异位词
简单
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
class Solution242: def func242(self, s, t): s1 = Counter(s) t1 = Counter(t) return s1 == t1 s = Solution242() a = "rat" b = "car" print(s.func242(a, b))
五、268. 丢失的数字
简单
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
nums = [0, 1] print(sum(range(len(nums) + 1)) - sum(nums))
六、349. 两个数组的交集
简单
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
class Solution349: def func(self, nums1, nums2): nums1.sort() nums2.sort() i = 0 j = 0 res = [] while i < len(nums1) and j < len(nums2): if nums1[i] > nums2[j]: j += 1 elif nums1[i] < nums2[j]: i += 1 else: if nums1[i] not in res: res.append(nums1[i]) i += 1 j += 1 return res r = Solution349() nums1 = [1, 2, 2, 1] nums2 = [2, 2] print(r.func(nums1, nums2))七、350. 两个数组的交集 II
简单
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
class Solution350: def func(self, nums1, nums2): nums1.sort() nums2.sort() i = 0 j = 0 res = [] while i < len(nums1) and j < len(nums2): if nums1[i] > nums2[j]: j += 1 elif nums1[i] < nums2[j]: i += 1 else: res.append(nums1[i]) i += 1 j += 1 return res r = Solution350() nums1 = [1, 2, 2, 1] nums2 = [2, 2] print(r.func(nums1, nums2))
猜你喜欢
网友评论
- 搜索
- 最新文章
- 热门文章