力扣热题-100技巧专题经典题解析
力扣热题 100：技巧专题经典题解析
系列文章目录
在力扣（LeetCode）平台上，有一些题目需要特定的技巧来解决。今天，我们就来详细解析技巧专题中的几道经典题目，帮助大家更好地理解解题思路和技巧。
一、只出现一次的数字（题目 136）
1. 题目描述
给定一个非空整数数组，其中除了一个元素只出现一次外，其他元素都出现两次。找到那个只出现一次的元素。
2. 示例
示例 1：
输入：
nums = [2, 2, 1]
输出：
1
3. 解题思路
这道题主要考察位运算的应用。我们可以使用异或运算来找到只出现一次的数字。异或运算的性质是：一个数异或自己为 0，一个数异或 0 为自己。因此，遍历数组，将所有元素异或在一起，最终结果就是只出现一次的数字。
4. 代码实现（Java）
public class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，其中 n 是数组的长度。需要遍历数组一次。
- 空间复杂度 ：O(1)，只使用了常数级别的额外空间。
二、多数元素（题目 169）
1. 题目描述
给定一个大小为 n 的数组，找到出现次数大于 ⌊ n/2 ⌋ 的元素。
2. 示例
示例 1：
输入：
nums = [3, 2, 3]
输出：
3
3. 解题思路
这道题主要考察 Boyer-Moore 投票算法的应用。我们可以维护一个候选元素和其计数，遍历数组，如果当前元素与候选元素相同，则计数加 1，否则计数减 1。当计数为 0 时，更新候选元素为当前元素。
4. 代码实现（Java）
public class Solution {
public int majorityElement(int[] nums) {
int candidate = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == candidate) {
count++;
} else {
count--;
if (count == 0) {
candidate = nums[i];
count = 1;
}
}
}
return candidate;
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，其中 n 是数组的长度。需要遍历数组一次。
- 空间复杂度 ：O(1)，只使用了常数级别的额外空间。
三、颜色分类（题目 75）
1. 题目描述
给定一个包含红色、白色和蓝色的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色的顺序排列。用 0、1 和 2 分别表示红色、白色和蓝色。
2. 示例
示例 1：
输入：
nums = [2, 0, 2, 1, 1, 0]
输出：
[0, 0, 1, 1, 2, 2]
3. 解题思路
这道题主要考察三指针的应用。我们可以使用三个指针，分别指向当前红色、白色和蓝色的位置。遍历数组，根据元素的值交换到相应的位置。
4. 代码实现（Java）
public class Solution {
public void sortColors(int[] nums) {
int red = 0, white = 0, blue = nums.length - 1;
while (white <= blue) {
if (nums[white] == 0) {
swap(nums, red, white);
red++;
white++;
} else if (nums[white] == 1) {
white++;
} else {
swap(nums, white, blue);
blue--;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，其中 n 是数组的长度。需要遍历数组一次。
- 空间复杂度 ：O(1)，只使用了常数级别的额外空间。
四、下一个排列（题目 31）
1. 题目描述
给定一个整数数组，重新排列成字典序的下一个排列。如果不存在下一个排列，则重新排列成最低的排列。
2. 示例
示例 1：
输入：
nums = [1, 2, 3]
输出：
[1, 3, 2]
3. 解题思路
这道题主要考察数组的操作和排列的生成。我们可以按照以下步骤生成下一个排列：
- 从后向前找到第一个可以增大的数。
- 从后向前找到第一个比该数大的数，并交换。
- 将该数后面的部分反转，使其最小。
4. 代码实现（Java）
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1, nums.length - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}5. 复杂度分析
- 时间复杂度 ：O(n)，其中 n 是数组的长度。需要遍历数组多次，但每次操作都是线性时间。
- 空间复杂度 ：O(1)，只使用了常数级别的额外空间。
五、寻找重复数（题目 287）
1. 题目描述
给定一个包含 n + 1 个整数的数组，其中每个元素在 1 到 n 之间，至少存在一个重复元素。找到那个重复的元素。
2. 示例
示例 1：
输入：
nums = [1, 3, 4, 2, 2]
输出：
2
3. 解题思路
这道题主要考察二分查找的应用。我们可以使用二分查找来确定重复元素。具体步骤如下：
- 初始化左右边界为 1 和 n。
- 计算中间值 mid，统计数组中小于等于 mid 的元素个数。
- 如果个数大于 mid，则重复元素在左半部分，否则在右半部分。
- 重复步骤 2 和 3，直到找到重复元素。
4. 代码实现（Java）
public class Solution {
public int findDuplicate(int[] nums) {
int left = 1, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int count = 0;
for (int num : nums) {
if (num <= mid) {
count++;
}
}
if (count > mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}5. 复杂度分析
- 时间复杂度 ：O(n log n)，其中 n 是数组的长度。二分查找的时间复杂度为 O(log n)，每次统计个数的时间复杂度为 O(n)。
- 空间复杂度 ：O(1)，只使用了常数级别的额外空间。
以上就是力扣热题 100 中与技巧相关的经典题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。
