【算法题解】 Day21 查找
剑指 Offer 04. 二维数组中的查找
题目
剑指 Offer 04. 二维数组中的查找 难度：medium
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
方法一：直接查找
思路
我们直接遍历整个矩阵 matrix，判断 target是否出现即可。
解题
Python：
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
for row in matrix:
for element in row:
if element == target:
return True
return FalseJava：
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
for (int[] row : matrix) {
for (int element : row) {
if (element == target) {
return true;
}
}
}
return false;
}
}方法二：二分查找
思路
由于矩阵 matrix中每一行的元素都是升序排列的，因此我们可以对每一行都使用一次二分查找，判断 target 是否在该行中，从而判断 target 是否出现。
解题
Python：
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
for row in matrix:
idx = bisect.bisect_left(row, target)
if idx < len(row) and row[idx] == target:
return True
return FalseJava：
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
for (int[] row : matrix) {
int index = search(row, target);
if (index >= 0) {
return true;
}
}
return false;
}
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
}剑指 Offer 50. 第一个只出现一次的字符
题目
剑指 Offer 50. 第一个只出现一次的字符 难度：easy
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:
输入：s = "abaccdeff"
输出：'b'示例 2:
输入：s = ""
输出：' '限制：
0 <= s 的长度 <= 50000
方法一：使用哈希表存储频数
思路
我们可以对字符串进行两次遍历。
在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回该字符，否则在遍历结束后返回空格。
解题
Python：
class Solution:
def firstUniqChar(self, s: str) -> str:
frequency = collections.Counter(s)
for i, ch in enumerate(s):
if frequency[ch] == 1:
return ch
return ' 'Java：
class Solution {
public char firstUniqChar(String s) {
Map<Character, Integer> frequency = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < s.length(); ++i) {
if (frequency.get(s.charAt(i)) == 1) {
return s.charAt(i);
}
}
return ' ';
}
}方法二：使用哈希表存储索引
思路
我们可以对方法一进行修改，使得第二次遍历的对象从字符串变为哈希映射。
具体地，对于哈希映射中的每一个键值对，键表示一个字符，值表示它的首次出现的索引（如果该字符只出现一次）或者 −1（如果该字符出现多次）。当我们第一次遍历字符串时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c 与它的索引作为一个键值对加入哈希映射中，否则我们将 c 在哈希映射中对应的值修改为 -1。
在第一次遍历结束后，我们只需要再遍历一次哈希映射中的所有值，找出其中不为 -1 的最小值，即为第一个不重复字符的索引，然后返回该索引对应的字符。如果哈希映射中的所有值均为 -1，我们就返回空格。
解题
Python：
class Solution:
def firstUniqChar(self, s: str) -> str:
position = dict()
n = len(s)
for i, ch in enumerate(s):
if ch in position:
position[ch] = -1
else:
position[ch] = i
first = n
for pos in position.values():
if pos != -1 and pos < first:
first = pos
return ' ' if first == n else s[first]Java：
class Solution {
public char firstUniqChar(String s) {
Map<Character, Integer> position = new HashMap<Character, Integer>();
int n = s.length();
for (int i = 0; i < n; ++i) {
char ch = s.charAt(i);
if (position.containsKey(ch)) {
position.put(ch, -1);
} else {
position.put(ch, i);
}
}
int first = n;
for (Map.Entry<Character, Integer> entry : position.entrySet()) {
int pos = entry.getValue();
if (pos != -1 && pos < first) {
first = pos;
}
}
return first == n ? ' ' : s.charAt(first);
}
}