下一个排列
解法一
双向遍历
先找出最大的索引 k 满足 nums[k] < nums[k+1]，如果不存在，就翻转整个数组；
再找出另一个最大索引 l 满足 nums[l] > nums[k]；
交换 nums[l] 和 nums[k]；
最后翻转 nums[k+1:]。
class Solution { public void nextPermutation(int[] nums) { int len = nums.length; if(len <= 1) return; int index = -1; for(int i = len-1;i>0;i--){ if(nums[i-1] < nums[i]){ index = i-1; break; } } if(index == -1){ // 说明这是递减序列 int left = 0; int right = len-1; while(left < right){ int temp = nums[right]; nums[right] = nums[left]; nums[left] = temp; left++; right--; } }else{ for(int i = len-1;i > index;i--){ if(nums[i] > nums[index]){ int temp = nums[i]; nums[i] = nums[index]; nums[index] = temp; Arrays.sort(nums,index+1,len); return; } } } return; } }
颜色分类
方法一
排序
冒泡、快速等都可以
class Solution { public void sortColors(int[] nums) { int len = nums.length; if(len <= 1) return; int p0 = 0,p2 = len-1; for(int i = 0;i < len;i++){ while(i <= p2 && nums[i] == 2){ int t = nums[p2]; nums[p2--] = nums[i]; nums[i] = t; } if(nums[i] == 0){ int t = nums[i]; nums[i] = nums[p0]; nums[p0++] = t; } } return; } }
方法二
双指针
class Solution { public void sortColors(int[] nums) { int len = nums.length; if(len <= 1) return; int p0 = 0,p2 = len-1; for(int i = 0;i < len;i++){ while(i <= p2 && nums[i] == 2){ int t = nums[p2]; nums[p2--] = nums[i]; nums[i] = t; } if(nums[i] == 0){ int t = nums[i]; nums[i] = nums[p0]; nums[p0++] = t; } } return; } }
寻找重复数
解法一
原地Hash
将值为x的放到下标为x-1处
class Solution { public int findDuplicate(int[] nums) { // num[i] = i+1 for(int i = 0;i < nums.length;i++){ while(nums[i] != i+1){ //值为nums[i]的应该放在nums[nums[i]-1] 处 if(nums[i] == nums[nums[i]-1]) return nums[i]; int t = nums[nums[i]-1]; nums[nums[i]-1] = nums[i]; nums[i] = t; } } return 0; } }
解法二
快慢指针
class Solution { public int findDuplicate(int[] nums) { int slow = 0; int fast = 0; do{ slow = nums[slow]; fast = nums[nums[fast]]; }while(slow != fast); slow = 0; while(slow != fast){ slow = nums[slow]; fast = nums[fast]; } return slow; } }
