• 【每日力扣】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
  • 相关阅读:
    【C语音 || 数据结构】二叉树--堆
    Json“牵手”唯品会商品详情数据方法,唯品会商品详情API接口,唯品会API申请指南
    Linux(常用命令)
    ActiveMQ 反序列化漏洞(CVE-2015-5254)特征分析
    C++11(下)
    【开源】基于Vue和SpringBoot的服装店库存管理系统
    SSM学习——SSM整合案例(Spring+SpringMVC+Mybatis)(13)
    SpringCloud-Config
    【MySQL】学习多表查询和笛卡尔积
    从零开始搭建搜索推荐系统(五十二)ElasticSearch搜索利器
  • 原文地址:https://blog.csdn.net/m0_69383623/article/details/138115358