• 【每日力扣】41. 缺失的第一个正数 238. 除自身以外数组的乘积 189. 轮转数组


    在这里插入图片描述

    🔥 个人主页: 黑洞晓威
    😀你不必等到非常厉害,才敢开始,你需要开始,才会变的非常厉害

    41. 缺失的第一个正数

    给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

    请你实现时间复杂度O(n) 并且只使用常数级别额外空间的解决方案。

    解题思路

    要找到未排序的整数数组中没有出现的最小正整数,并且要求使用 O(n) 时间复杂度和常数级别额外空间,可以通过数组索引的映射来实现。

    1. 首先遍历数组,将所有正整数放到对应的索引位置,负数和大于数组长度的数无需处理。
    2. 然后再次遍历数组,查找第一个索引位置与数值不对应的情况,这个索引加 1 即为缺失的最小正整数。

    代码实现

    class Solution {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
    
            // 将所有正整数放到对应的索引位置
            for (int i = 0; i < n; i++) {
                while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                    int temp = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = temp;
                }
            }
    
            // 查找第一个索引位置与数值不对应的情况
            for (int i = 0; i < n; i++) {
                if (nums[i] != i + 1) {
                    return i + 1;
                }
            }
    
            return n + 1;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    238. 除自身以外数组的乘积

    给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积

    题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

    请 **不要使用除法,**且在 O(*n*) 时间复杂度内完成此题。

    解题思路

    在不使用除法并且在 O(n) 时间复杂度内完成此题的要求下,可以使用两次遍历来实现。具体思路如下:

    1. 第一次遍历:从左向右计算每个元素左边所有元素的乘积,保存在一个数组中。
    2. 第二次遍历:从右向左计算每个元素右边所有元素的乘积,与第一步中计算的结果相乘得到最终结果。

    代码实现

    class Solution {
        public int[] productExceptSelf(int[] nums) {
            int n = nums.length;
            int[] result = new int[n];
            
            // 第一次遍历,计算每个元素左边所有元素的乘积
            int left = 1;
            for (int i = 0; i < n; i++) {
                result[i] = left;
                left *= nums[i];
            }
            
            // 第二次遍历,右边所有元素的乘积与之前计算的结果相乘得到最终结果
            int right = 1;
            for (int i = n - 1; i >= 0; i--) {
                result[i] *= right;
                right *= nums[i];
            }
            
            return result;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    189. 轮转数组

    给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

    解题思路

    要将数组中的元素向右轮转k个位置,可以通过三次反转数组的操作来实现。

    1. 将整个数组反转。
    2. 将前k个元素反转。
    3. 将剩余的n-k个元素反转。

    代码实现

    class Solution {
        public void rotate(int[] nums, int k) {
            int n = nums.length;
            k = k % n; // 如果k大于数组长度,取余数
    
            // 翻转整个数组
            reverse(nums, 0, n - 1);
            
            // 翻转前k个元素
            reverse(nums, 0, k - 1);
            
            // 翻转剩余的元素
            reverse(nums, k, n - 1);
        }
        
        private void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start++;
                end--;
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
  • 相关阅读:
    【Mysql】数据库第一讲(服务器数据库的安装和基础操作介绍)
    Guava缓存及Guava线程池
    Jenkins配置钉钉通知
    学习二十大奋进新征程线上知识答题活动回顾
    OPENCV实现暴力特征匹配
    图片引用功能导致的XSS漏洞
    7 和其他程序协同工作
    C语言适不适合新手学习?
    Python 考试练习题 1
    无版权 NFT 会为市场带来改变么?
  • 原文地址:https://blog.csdn.net/m0_69383623/article/details/138115358