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

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

下一个排列


d1f2998dcc2f494399126583621a2cbf.png

解法一

双向遍历

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

颜色分类


967fb25073af4a3cb6abcc1910548d44.png


方法一

排序

冒泡、快速等都可以

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;
    }
}


寻找重复数


6af33f911f95433e85869f91c5680cbf.png

解法一

原地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;
    }
}


目录
打赏
0
0
0
0
4
分享
相关文章
|
9月前
输入三个数从小到大排列
输入三个数从小到大排列
52 0
|
8月前
|
现有‘abcdefghijkl’12个字符,将其所有的排列按字典序进行排序,给出任意一组排列,说出这租排列在所有排列中是第几小的
现有‘abcdefghijkl’12个字符,将其所有的排列按字典序进行排序,给出任意一组排列,说出这租排列在所有排列中是第几小的
76 1
判断晨曦酒庄的酒桶能否恰好装满给定的葡萄酒
晨曦酒庄有 n 个酒桶,容量分别是从 1 到 n(升),他可以从中任意挑选 k 个酒桶,并且每个酒桶必须恰好装满。 现在迪卢克准备了 x 升葡萄酒,判断能否用 k 个酒桶装满。
63 1
|
9月前
代码随想录Day30 贪心05 LeetCode T435无重叠区间 T763划分字母区间 T56 合并区间
代码随想录Day30 贪心05 LeetCode T435无重叠区间 T763划分字母区间 T56 合并区间
63 0
7 种 基本比例尺地形图的分幅和编号的数量关系
7 种 基本比例尺地形图的分幅和编号的数量关系
1261 0
7 种 基本比例尺地形图的分幅和编号的数量关系
leetcode-每日一题1252. 奇数值单元格的数目(模拟优化)
时间复杂度:O(q * (m + n) + m * n) 其中q表示 indices 数组的长度,m、n为矩阵的行数和列数,遍历 indices 数组都要更新一次行列,总共需要O(q * (m + n))的时间,最后遍历一次矩阵,总共需要O(m * n)的时间
77 0
leetcode-每日一题1252. 奇数值单元格的数目(模拟优化)
每日三题-旋转图像、合并区间、除自身以外数组的乘积
每日三题-旋转图像、合并区间、除自身以外数组的乘积
83 0
每日三题-旋转图像、合并区间、除自身以外数组的乘积
每日三题-数组中的第K个最大元素、滑动窗口最大值、前K个高频元素
每日三题-数组中的第K个最大元素、滑动窗口最大值、前K个高频元素
117 0
每日三题-数组中的第K个最大元素、滑动窗口最大值、前K个高频元素
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等