136.只出现一次的数字给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。class Solution { public int singleNumber(int[] nums) { int single 0; for (int num : nums) { single single ^ num; //把数转化为二进制0/1进行异或 //相同为0不同为1 //0^xx } 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) { MapInteger, 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. 反转 i1 到末尾 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; } }