剑指Offer 3900 数组中出现次数超过一半的数字（摩尔投票） (简单, 2021-12)剑指Offer 4000 最小的k个数（partition操作） (简单, 2021-12)剑指Offer 4500 把数组排成最小的数 (中等, 2021-12)剑指Offer 6100 扑克牌中的顺子 (简单, 2022-01)剑指Offer2 076 数组中的第K大的数字 (中等, 2022-02)牛客 0037 合并区间 (中等, 2022-02)程序员面试金典 0101 判定字符是否唯一 (简单, 2022-01)
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。详细描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 排序后，数组中间位置的数一定满足题意；
- 时间复杂度
O(NlogN)；
Python
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums) // 2]- 一次遍历，记录每个数出现的次数；
- 空间复杂度
O(N)；
Python
class Solution:
def majorityElement(self, nums: List[int]) -> int:
from collections import defaultdict
cnt = defaultdict(int)
for x in nums:
cnt[x] += 1
if cnt[x] > len(nums) // 2:
return x
# return -1- “摩尔投票法”的核心思想是一一抵消；
- 假设已知目标数为 x，遍历时若出现一次 x 记
+1票，否则为-1票；- 推论1：最终票数和必大于 0；
- 推论2：若前 n 个数的票数和为 0，那么剩余部分依然满足推论1，即目标数字依然为 x；
Python
class Solution:
def majorityElement(self, nums: List[int]) -> int:
cnt = 0
for x in nums:
if cnt == 0: # 当票数和为 0 时，假设当前值为目标值
ret = x # 如果这个数不是目标值，那么它迟早会因为不断 -1，被替换掉
if x == ret:
cnt += 1
else:
cnt -= 1
return ret- 本题使用分治在时间和空间上都不是最优，仅用于理解分治的思想；
Python
class Solution:
def majorityElement(self, nums: List[int]) -> int:
def recur(lo, hi): # [lo, hi] 闭区间
if lo == hi: # 当数组中只有一个元素时，这个数就是目标值
return nums[lo]
# 分治
mid = (hi - lo) // 2 + lo
l = recur(lo, mid)
r = recur(mid + 1, hi)
# 如果左右返回值相同时，显然这个值就是目标值
if l == r:
return l
# 否则需要判断哪个出现的次数更多
lc = sum(1 for i in range(lo, hi + 1) if nums[i] == l)
rc = sum(1 for i in range(lo, hi + 1) if nums[i] == r)
return l if lc > rc else r
return recur(0, len(nums) - 1)
输入整数数组 arr ，找出其中最小的 k 个数详细描述
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 快排的过程：
- partition 过程：以数组某个元素（一般取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
- 递归地对左右部分执行 partition 过程，直至区域内的元素数量为 1；
- 基于以上思想，当某次划分后基准数正好是第 k+1 小的数字，那么此时基准数左边的所有数字便是题目要求的最小的 k 个数。
Python
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
def partition(lo, hi): # [lo, hi]
if lo >= hi: return
p = arr[lo] # 选取第一个位置为基准点
l, r = lo, hi # l 的初始位置应该在 lo，而不是 lo + 1
# 假设初始化为 lo + 1，当 a[lo] 为最小值时，此时训处循环后 l == r == lo + 1，再交换 a[lo] 和 a[l] 就会出错
while l < r: # 退出循环时 l == r
# 先移动 r，在移动 l，此时退出循环后 l 和 r 同时指向一个小于 p 的值；反之，如果用 a[hi] 初始化 p，就要先移动 l，在移动 r；
# 从 r 开始，从右往左找到第一个 < p 的值，所以循环条件是 >=
while l < r and arr[r] >= p: r -= 1
# 从 l 开始，从左往右找到第一个 > p 的值，所以循环条件是 <=
while l < r and arr[l] <= p: l += 1
arr[l], arr[r] = arr[r], arr[l]
arr[lo], arr[l] = arr[l], arr[lo] # 将基准点移动到分界点
if l < k: partition(l + 1, hi)
if l > k: partition(lo, l - 1)
partition(0, len(arr) - 1)
return arr[:k]- 写法1） 维护一个长度为 k 的大顶堆（第一个数最大），当下一个元素小于堆顶值，就更新堆（弹出堆顶，插入新值）；
- 写法2） 直接对整个数组构建一个小顶堆，然后循环弹出前 k 个值；
- 注意写法1 的时间复杂度是
O(NlogK)，而写法2 是O(NlogN)；
Python：写法1（使用库函数）
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k < 1 or not arr: # 使用堆，要添加非空断言
return []
import heapq
# python 默认是小顶堆，且不支持自定义比较函数，所以要添加负号转成取前 k 大的数
ret = [-x for x in arr[:k]]
heapq.heapify(ret)
for i in range(k, len(arr)):
if -arr[i] > ret[0]:
heapq.heappop(ret)
heapq.heappush(ret, -arr[i])
return [-x for x in ret]Python：写法2（使用库函数）
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k < 1 or not arr: # 使用堆，要添加非空断言
return []
import heapq
# python 默认是小顶堆
heapq.heapify(arr)
ret = []
for _ in range(k):
ret.append(heapq.heappop(arr))
return ret- 因为题目限制了
arr[i]的范围，所以还可以使用计数排序，时间复杂度O(N)；
Python
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k >= len(arr): # 使用计数排序要加长度判断
return arr
dp = [0] * 10001
for x in arr:
dp[x] += 1
ret = []
cnt = 0
for i in range(len(dp)):
while dp[i] and cnt < k:
ret.append(i)
cnt += 1
dp[i] -= 1
if cnt == k:
return ret
xxx详细描述
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。-
算法基于以下结论：若
x + y < y + x则x应该排在y前面/左边； -
关于该结论的证明详见：把数组排成最小的数
-
根于该规则对
nums排序后拼接即可；
Python：使用库函数
import functools
class Solution:
def minNumber(self, nums: List[int]) -> str:
def cmp(x1, x2):
if x1 + x2 < x2 + x1:
return -1
elif x1 + x2 > x2 + x1:
return 1
else:
return 0
# Python3 的 sort 中取消了 cmp 参数，需要通过 functools.cmp_to_key 转换
nums = sorted([str(x) for x in nums], key=functools.cmp_to_key(cmp))
# print(nums)
return ''.join(nums)Python：手动实现排序（快排）
class Solution:
def minNumber(self, nums: List[int]) -> str:
nums = [str(x) for x in nums]
def qsort(lo, hi):
if lo >= hi: return
i, j = lo, hi
while i < j:
while nums[j] + nums[lo] >= nums[lo] + nums[j] and i < j: j -= 1
while nums[i] + nums[lo] <= nums[lo] + nums[i] and i < j: i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i], nums[lo] = nums[lo], nums[i]
qsort(lo, i - 1)
qsort(i + 1, hi)
qsort(0, len(nums) - 1)
return ''.join(nums)
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子；详细描述
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
限制：
数组长度为 5
数组的数取值为 [0, 13] .
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 排序后，统计 0 出现的次数，以及数组中的
max_x和min_x； - 当
最大值 - 最小值 < 5时即可组成顺子； - 若出现相同牌则提前返回 False；
Python
class Solution:
def isStraight(self, nums: List[int]) -> bool:
nums.sort() # 排序
# 如果不想排序需的话，就需要另外使用一些变量来记录最大、最小和已经出现过的牌
cnt_0 = 0
for i, x in enumerate(nums[:-1]):
if x == 0: # 记录 0 的个数
cnt_0 += 1
elif x == nums[i + 1]:
return False
# return nums[-1] - nums[cnt_0] == 4 # Error，因为 0 也可以用来作为最大或最小的牌
return nums[-1] - nums[cnt_0] < 5
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。详细描述
给定整数数组 nums 和整数 k，请返回数组中第 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
提示：
1 <= k <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xx4gT2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。思路1：partition操作（分治）
- partition操作描述：先随机确定一个锚点，然后将数组划分为小于锚点和大于锚点的两部分呢；
import random
class Solution:
""""""
def findKthLargest(self, nums: List[int], k: int) -> int: # noqa
""""""
lo, hi = 0, len(nums) - 1
while True: # 第 k 大，排序后期下标应该是 k - 1
idx = self.partition(nums, lo, hi)
if idx + 1 == k:
return nums[idx]
elif idx + 1 < k:
lo = idx + 1
else:
hi = idx - 1
def partition(self, nums: List[int], lo: int, hi: int) -> int:
""""""
# === 挑选锚点 ===
# 方式1）默认选 lo 作为锚点
# pivot = nums[lo]
# 方式2）随机选择一个锚点，并把锚点固定到首位或末位，这里交换到首位
flag = random.randint(lo, hi)
pivot = nums[flag]
nums[flag], nums[lo] = nums[lo], nums[flag]
# === partition 操作 ===
# 方式1）单向遍历
idx = lo # 记录锚点在数组中的升序顺位
for i in range(lo + 1, hi + 1):
if nums[i] > pivot: # 找到一个大于锚点的值
idx += 1
nums[idx], nums[i] = nums[i], nums[idx]
nums[idx], nums[lo] = nums[lo], nums[idx] # 把锚点交换到 idx 的位置
return idx
# 方式2）左右交换
# l, r = lo, hi
# while l < r:
# while l < r and nums[r] <= pivot:
# r -= 1
# while l < r and nums[l] >= pivot:
# l += 1
# if l < r:
# nums[l], nums[r] = nums[r], nums[l]
# nums[lo], nums[l] = nums[l], nums[lo]
#
# return l思路2：大顶堆（Python，调库）
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
""""""
heap = []
for x in nums:
heapq.heappush(heap, -x) # 默认是小顶堆，这里传入 -x，模拟大顶堆
for _ in range(k - 1):
heapq.heappop(heap)
return -heap[0]
给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。- 按开始节点排序，则可以合并的部分必是连续的，然后根据题意模拟即可；
Python
# class Interval:
# def __init__(self, a=0, b=0):
# self.start = a
# self.end = b
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param intervals Interval类一维数组
# @return Interval类一维数组
#
class Solution:
def merge(self , intervals: List[Interval]) -> List[Interval]:
# write code here
if not intervals: return []
a = sorted(intervals, key=lambda x: (x.start, x.end))
ret = [a[0]]
for it in a[1:]:
pre = ret[-1]
if it.start > pre.end:
ret.append(it)
else:
pre.end = max(pre.end, it.end)
return ret
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
不使用额外的数据结构详细描述
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
输入: s = "leetcode"
输出: false
示例 2：
输入: s = "abc"
输出: true
限制：
0 <= len(s) <= 100
如果你不使用额外的数据结构，会很加分。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-unique-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 因为要求不使用额外数据结构，因此可以考虑排序后，顺序两两比较；
- 注意边界条件；
Python
class Solution:
def isUnique(self, astr: str) -> bool:
if not astr: return True
cs = sorted(astr)
pre = cs[0]
for c in cs[1:]:
if pre == c:
return False
pre = c
return True