每日三题-下一个排列、颜色分类、寻找重复数

才疏学浅的木子

发布于 2022-11-20 08:45:59

19400

代码可运行

运行总次数：0

代码可运行

👨‍💻个人主页： 才疏学浅的木子 🙇‍♂️ 本人也在学习阶段如若发现问题，请告知非常感谢 🙇‍♂️ 📒 本文来自专栏： 算法 🌈 算法类型：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;
    }
}