136.只出现一次的数字

给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

class Solution { public int singleNumber(int[] nums) { int single = 0; for (int num : nums) { single = single ^ num; //把数转化为二进制0/1进行异或 //相同为0，不同为1 //0^x=x } return single; } }

169.多数元素

给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution { public int majorityElement(int[] nums) { int count = 0; int res = 0; for (int num : nums) { if (count == 0) { res = num; } if (num == res) { count++; } else { count--; } } return res; } }

import java.util.Arrays; class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; } }

import java.util.HashMap; import java.util.Map; class Solution { public int majorityElement(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); int half = nums.length / 2; for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); if (map.get(num) > half) { return num; } } return -1; } }

75.颜色分类

给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数0、1和2分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

class Solution { public void sortColors(int[] nums) { int low = 0, mid = 0, high = nums.length - 1; while (mid <= high) { if (nums[mid] == 0) { swap(nums, low, mid); low++; mid++; } else if (nums[mid] == 1) { mid++; } else { swap(nums, mid, high); high--; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

31.下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3]的下一个排列是[1,3,2]。
• 类似地，arr = [2,3,1]的下一个排列是[3,1,2]。
• 而arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。

给你一个整数数组nums，找出nums的下一个排列。

必须原地修改，只允许使用额外常数空间。

class Solution { public void nextPermutation(int[] nums) { int n = nums.length; // 1. 从右往左找到第一个 nums[i] < nums[i + 1] 的位置 int i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } // 2. 如果找到了拐点，继续从右往左找第一个比 nums[i] 大的数 if (i >= 0) { int j = n - 1; while (j >= 0 && nums[j] <= nums[i]) { j--; } swap(nums, i, j); } // 3. 反转 i+1 到末尾 reverse(nums, i + 1, n - 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 left, int right) { while (left < right) { swap(nums, left, right); left++; right--; } } }

287.寻找重复数

给定一个包含n + 1个整数的数组nums，其数字都在[1, n]范围内（包括1和n），可知至少存在一个重复的整数。

假设nums只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组nums且只用常量级O(1)的额外空间。

class Solution { public int findDuplicate(int[] nums) { // 阶段1：快慢指针找到相遇点 int slow = nums[0]; int fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); // 阶段2：找环入口 slow = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } }