【LeetCode刷题记录】238. 除自身以外数组的乘积

2024-04-14 23:04

本文主要是介绍【LeetCode刷题记录】238. 除自身以外数组的乘积,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

238 除自身以外数组的乘积

给你一个整数数组 nums,返回数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。
请不要使用除法,且在 O(n) 时间复杂度内完成此题。

示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示:
2 < = n u m s . l e n g t h < = 1 0 5 2 <= nums.length <= 10^5 2<=nums.length<=105
− 30 < = n u m s [ i ] < = 30 -30 <= nums[i] <= 30 30<=nums[i]<=30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶:你可以在 O(1) 的额外空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

思路

(1)常规思路——使用除法:
根据题意分析可得到以下结论:
若数组中含1个0元素,那么除了该元素对应值为其他元素乘积,其余乘积均为0,只要记录该0元素位置赋值即可;
若数组中含2个0元素,那么输出的乘积全为0;
若数组不含0元素,那么每个元素对应乘积为总乘积除以该元素。
(2)不用除法:
题目要求不使用除法,那么可以使用前缀和思想,只是应用到这里变成了前缀积。
根据题意得知:每个元素对应乘积等于=左侧元素乘积*右侧元素乘积。
那么只需计算每个元素左侧的所有元素乘积——前缀积 l ( n ) l(n) l(n) 和每个元素右侧的所有元素乘积——后缀积 r ( n ) r(n) r(n)即可。

代码

法一:

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int product = 1;vector<int> v(nums.size());// cnt记录0元素个数,pos记录唯一零元素位置int cnt = 0, pos = -1;for (int i = 0; i < nums.size(); i++) {if (nums[i] != 0) {product *= nums[i];} else {pos = i;cnt++;}}if (cnt > 1) {// 将v全部赋值为0fill(v.begin(), v.end(), 0);return v;} else if (cnt == 1) {// 除了唯一零元素对应位置是其他元素乘积,其他元素都是0v[pos] = product;return v;} else {for (int i = 0; i < nums.size(); i++) {v[i] = product / nums[i];}return v;}}
};

法二:

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();// 分别记录i元素的前缀积和后缀积(不包括i)vector<int> l(n), r(n), v;l[0] = 1, r[n - 1] = 1;for (int i = 1; i < n; i++) {l[i] = nums[i - 1] * l[i - 1];}for (int i = n - 2; i >= 0; i--) {r[i] = nums[i + 1] * r[i + 1];}for (int i = 0; i < n; i++) {v.push_back(l[i] * r[i]);}return v;}
};

这篇关于【LeetCode刷题记录】238. 除自身以外数组的乘积的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/904267

相关文章

Zabbix在MySQL性能监控方面的运用及最佳实践记录

《Zabbix在MySQL性能监控方面的运用及最佳实践记录》Zabbix通过自定义脚本和内置模板监控MySQL核心指标(连接、查询、资源、复制),支持自动发现多实例及告警通知,结合可视化仪表盘,可有效... 目录一、核心监控指标及配置1. 关键监控指标示例2. 配置方法二、自动发现与多实例管理1. 实践步骤

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

在Spring Boot中集成RabbitMQ的实战记录

《在SpringBoot中集成RabbitMQ的实战记录》本文介绍SpringBoot集成RabbitMQ的步骤,涵盖配置连接、消息发送与接收,并对比两种定义Exchange与队列的方式:手动声明(... 目录前言准备工作1. 安装 RabbitMQ2. 消息发送者(Producer)配置1. 创建 Spr

k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)

《k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)》本文记录在K8s上运行的MySQL/MariaDB备份方案,通过工具容器执行mysqldump,结合定时任务实... 目录前言一、获取需要备份的数据库的信息二、备份步骤1.准备工作(X86)1.准备工作(arm)2.手

SpringBoot3应用中集成和使用Spring Retry的实践记录

《SpringBoot3应用中集成和使用SpringRetry的实践记录》SpringRetry为SpringBoot3提供重试机制,支持注解和编程式两种方式,可配置重试策略与监听器,适用于临时性故... 目录1. 简介2. 环境准备3. 使用方式3.1 注解方式 基础使用自定义重试策略失败恢复机制注意事项

Python UV安装、升级、卸载详细步骤记录

《PythonUV安装、升级、卸载详细步骤记录》:本文主要介绍PythonUV安装、升级、卸载的详细步骤,uv是Astral推出的下一代Python包与项目管理器,主打单一可执行文件、极致性能... 目录安装检查升级设置自动补全卸载UV 命令总结 官方文档详见:https://docs.astral.sh/

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

统一返回JsonResult踩坑的记录

《统一返回JsonResult踩坑的记录》:本文主要介绍统一返回JsonResult踩坑的记录,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录统一返回jsonResult踩坑定义了一个统一返回类在使用时,JsonResult没有get/set方法时响应总结统一返回