136.只出现一次的数字
位运算，异或
异或特点：
- 交换律
- 结合律
- 自身异或为 0
- 与 0 异或不变
//136. 只出现一次的数字
public class SingleNumber_136 {
static class Solution {
//异或运算有加法律和结合律;自身异或为0；与0异或不变
public int singleNumber(int[] nums) {
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
result=result^nums[i];
}
return result;
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {4, 1, 2, 1, 2};
int single = solution.singleNumber(nums);
System.out.println("只出现一次的数字是: " + single);
}
}169.多数元素
public static int majorityElement(int[] nums) {
//有已知条件：数组非空、存在多数元素。有因为出现次数 大于 ⌊ n/2 ⌋ ，所以有且仅有一个多数元素。
//遍历所有元素，不相同的抵消，剩下的就是只有所求的“多数元素”。
//抵消操作：对于当前元素计数count，遇到相同元素，计数+1，遇到不同的元素，计数-1；当计数为0时，将当前元素作为新的候选元素。
int count = 0;
int current = 0;
for (int i = 0; i < nums.length; i++) {
if (count==0){
current=nums[i];
}
if (nums[i]==current){
count++;
}else {
count--;
}
}
return current;
}75.颜色分类：
核心思想：
- 使用三个指针划分区域：0 的区域、1 的区域和 2 的区域
zero指针：指向 0 区域的下一个位置（即下一个 0 应该放置的位置）two指针：指向 2 区域的前一个位置（即下一个 2 应该放置的位置）i指针：用于遍历数组
- 初始化
zero为 0，two为数组末尾索引 - 遍历数组，当
i超过two时结束 - 若当前元素是 2，则与
two指针位置元素交换，two左移（因为交换过来的元素可能还是 2，需要继续检查 - 若当前元素是 0，则与
zero指针位置元素交换，zero右移，i右移 - 若当前元素是 1，直接
i右移
因为i从前往后，zero也从前往后，所以zero换过去和换过来的值知道。而two是从后往前，换过来的可能还是0、2 。所以需要while循环检查处理，而对零的判断处理也因此要放在对2处理的后面。
public static void sortColors(int[] nums) {
int zero = 0;
int two =nums.length-1;
for (int i = 0; i <= two; i++) {
while (nums[i]==2 && i<=two){
int temp = nums[i];
nums[i] = nums[two];
nums[two] = temp;
two--;
}
if (nums[i]==0){
int temp = nums[i];
nums[i] = nums[zero];
nums[zero] = temp;
zero++;
}
}
}31.下一个排序：
整体思路
- 从后向前找第一个“升序对”
找到最大索引i，使得nums[i] < nums[i + 1]
说明从i+1开始是一个 递减序列（即当前后缀最大） - 如果找到了这样的
i（即当前不是最大排列）：- 从后向前找最大索引
j，使得nums[j] > nums[i] - 交换
nums[i]与nums[j]
- 从后向前找最大索引
- 反转后缀（从
i+1到末尾）
把原本递减的后缀变为最小的升序排列，确保“刚刚大一点”
特殊情况
- 如果步骤 1 找不到任何
i（即全是递减的排列，如[5,4,3,2,1]），说明已经是最大排列
直接 反转整个数组，变成最小排列（升序）
举例：
| 步骤 | i | j | 数组状态 |
|---|---|---|---|
| 原始输入 | [1, 4, 5, 3, 2] | ||
| 找到 i | 1 | nums[1]=4 | |
| 找到 j | 2 | nums[2]=5 | |
| 交换 i 和 j | [1, 5, 4, 3, 2] | ||
| 翻转后缀 | [1, 5, 2, 3, 4] ✅ |
public static void nextPermutation(int[] nums) {
//1.找到第一个升序对：i，i+1
int i = nums.length-2;
while (i>=0 && nums[i]>=nums[i+1]){
i--;
}
if (i<0){
//说明是最大排序（降序），反转后即使所求的下一个排序（最小的）
reverse(nums,0,nums.length-1);
return;
}
//2.从后往前找第一个大于nums[i]的，同时也是最小的
int j = nums.length-1;
while (j>i && nums[j]<=nums[i]){
j--;
}
//3.调换i，j。
swap(nums,i,j);
//4.此时nums[i+1]到末尾是降序，反转为升序使其最小。
reverse(nums,i+1,nums.length-1);
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private static void reverse(int[] nums, int left, int right) {
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}287.寻找重复数
287. 寻找重复数
数学证明：
弗洛伊德循环检测算法（龟兔赛跑） – 内幕代码 – YouTube （弗洛伊德算法）_哔哩哔哩_bilibili
public static int findDuplicate(int[] nums) {
//快慢指针（龟兔赛跑 Floyd 判环算法）
//nums【i】的值就是下个元素的索引，这样就能构造出一个链表，而如果有重复元素，部分元素就会成环，使用快慢指针（龟兔赛跑 Floyd 判环算法）来找到这个重复元素
//初始化，兔子每次多跑一步
int slow = nums[nums[0]];
int fast = nums[nums[nums[0]]];
//S1：再环内相遇（不一定是重复点）
while(slow!=fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
// Step 2: 找到入环点（即重复的数字）
int ptr1 = nums[0];
int ptr2 = slow;
while (ptr1 != ptr2) {
ptr1 = nums[ptr1];
ptr2 = nums[ptr2];
}
return ptr1;
}