每日三题-下一个排列、颜色分类、寻找重复数
👨💻个人主页： 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题，请告知非常感谢 🙇♂️ 📒 本文来自专栏： 算法 🌈 算法类型：Hot100题 🌈 ❤️ 支持我：👍点赞 🌹收藏 🤟关注
每日三题
下一个排列
在这里插入图片描述
解法一
双向遍历 先找出最大的索引 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) {
Arrays.sort(nums);
}
}方法二
双指针
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;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-11-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
