统计一个数字在排序数组中出现的次数
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
- hash字典的方法，第一次遇见简历一个key，默认值为1
- 后续遇见该key，value += 1
class Solution:
def search(self, nums: List[int], target: int) -> int:
all_num = dict()
for i in nums:
if i not in all_num:
all_num[i] = 1
else:
all_num[i] += 1
if target in all_num:
return all_num[target]
return 0
数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
- 建立一个集合all_num用于无序、不重复储存数字
- 如果不在集合里，add； 如果集合中已存在，即为重复数
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
all_num = set()
for i in nums:
if i not in all_num:
all_num.add(i)
else:
return i
0～n-1中缺失的数字
- 通过数学公式解决，0～n-1求和 - 实际和
class Solution:
def missingNumber(self, nums: List[int]) -> int:
length = len(nums)
sum_exp = (1+length)*length//2
sum_ac = sum(nums)
return sum_exp - sum_ac
二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
image.png
- 利用二维数组的特性，仿二叉树进行操作
- 旋转，从右上角开始便利，index依次左右移动
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if matrix:
r = 0
c = len(matrix[0]) - 1
while r < len(matrix) and c >= 0 :
flag = matrix[r][c]
if flag == target:
return True
elif flag > target:
c -= 1
else:
r += 1
return False
else:
return False
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。
输入：[3,4,5,1,2]
输出：1
输入：[2,2,2,0,1]
输出：0
- 简单遍历，遇见second < first 即为找到最小值 second
class Solution:
def minArray(self, numbers: List[int]) -> int:
if len(numbers):
first = 0
second = 1
while second < len(numbers):
if numbers[first] > numbers[second]:
return numbers[second]
else:
first += 1
second += 1
return numbers[0]
- 二分法查找
- 通过比较mid和right的关系，分为三种情况：
-
若 mid < right，说明当前 mid～right这部分为单调递增，即最小值应该在当前mid左侧，更新right指针位置 = mid
image.png -
若 mid> right，说明mid～right部分肯定包含最小值，更新left指针为mid + 1
image.png - 若存在 mid == right，无法判定，因此右侧指针依次左移；
class Solution:
def minArray(self, numbers: List[int]) -> int:
# 初始化边界指针
left = 0
right = len(numbers) - 1
while right > left:
mid = left + (right-left) // 2
if numbers[mid] > numbers[right]:
# 5 6 7【10】11 1 min 3. --->10>3
# 11 1 min 3
left = mid + 1
elif numbers[mid] < numbers[right]:
# 10 11 12 2【3】4 6 8 --->3<8
# 10 11 12 2【3】
right = mid
else:
# 正常右侧指针左移 (可能存在重复元素)
# 10 7【10】10 10
# 10 7 10 10
right -= 1
return numbers[left]
第一个只出现一次的字母
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
输入：s = "abaccdeff"
输出：'b'
遍历一次构建字典，再便利一次输出第一个key=1的字母
- 其中生成计数字典也可以使用 frequency = collections.Counter(s)
class Solution:
def firstUniqChar(self, s: str) -> str:
if not s:
return " "
all_char = dict()
for char in s:
if char in all_char:
all_char[char] += 1
else:
all_char[char] = 1
for char in s:
if all_char[char] == 1:
return char
return " "
有序哈希表
- 使用 collections.OrderedDict() 简历有序哈希表，避免第二次遍历字符串
- 直接遍历 dic.items()，如果v=1，return k
哈希表存索引
- key = char， value = index
- 如果出现重复的， value赋值为 -1
- 遍历keys，存下最小的无重复char的index
class Solution:
def firstUniqChar(self, s: str) -> str:
positions = dict()
length = len(s)
for i in range(length):
char = s[i]
# 如果已经存在，那就返回-1（必不是要找的那个）
if char in positions:
positions[char] = -1
else:
positions[char] = i
first = length # 取不到这个值的，index最大值为length-1
for pos in positions.values():
if pos != -1 and pos < first:
# pos != -1： pos没有重复出现
# pos < first：比当前记录的idnex小，即为第一个出现的非重复
first = pos
return ' ' if first == length else s[first]
# first == n 即为没找到只出现一次的字符
