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

2022-12-06 55

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

下一个排列

解法一

双向遍历

先找出最大的索引 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;
    }
}