除自身以外数组的乘积[中等]

优质博文:IT-BLOG-CN
在这里插入图片描述

一、题目

给你一个整数数组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 <= nums.length <= 105
-30 <= nums[i] <= 30
保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32位整数范围内

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

二、代码

【1】创建左右乘积列表: 我们不能将所有数字的乘积除以给定索引处的数字得到相应的答案,而是利用索引左侧所有数字的乘积和右侧所有数字的乘积(即前缀与后缀)相乘得到答案。初始化两个数组LeftRight,对于指定的下表ileft[i]代表i左侧所有数据的乘积,right[i]代表i右侧所有数据的乘积。我们利用循环将数据填充到lfet[]right[]数组中,然后将left[i]right[i]相乘就是i的左右乘积。

class Solution {public int[] productExceptSelf(int[] nums) {if (nums == null || nums.length == 0) {return null;}// 我们使用数组,也就是当前数字的left[] 和 right[] 数组,分别存储左右两边的和;int len = nums.length;int res[] = new int[len];int left[] = new int[len];int right[] = new int[len];// 第一个数之前的数的乘积为1,所以先给个默认值left[0] = 1;for (int i = 1; i < len; i++) {// left 中保存的是i之前所有数的乘积left[i] = left[i - 1] * nums[i - 1];}// 最有边的数也保存为1right[len - 1] = 1;for (int i = len - 2; i >= 0; i--) {right[i] = right[i + 1] * nums[i + 1];}for (int i = 0; i < len; i++) {res[i] = left[i] * right[i];}return res;}
}

时间复杂度: O(N),其中N指的是数组nums的大小。预处理LR数组以及最后的遍历计算都是O(N)的时间复杂度。
空间复杂度: O(N),其中N指的是数组nums的大小。使用了LR数组去构造答案,LR数组的长度为数组nums的大小。

【2】空间复杂度O(1)的方法: 由于输出数组不算在空间复杂度内,那么我们可以将LR数组用输出数组来计算。先把输出数组当作L数组来计算,然后再动态构造R数组得到结果。

class Solution {public int[] productExceptSelf(int[] nums) {if (nums == null || nums.length == 0) {return null;}// 因为返回的数组可以不算在空间复杂度中,所以可以作为临时变量存放left[]数据int len = nums.length;int res[] = new int[len];// // 第一个数之前的数的乘积为1,所以先给个默认值res[0] = 1;for (int i = 1; i < len; i++) {// left 中保存的是i之前所有数的乘积res[i] = res[i - 1] * nums[i - 1];}// 然后从后向前变量,通过变量 right保存前几位数的乘积int right = 1;for (int i = len - 1; i >= 0; i--) {res[i] *= right;// 放在返回值的后面,就相当于i + 1right *= nums[i];} return res;}
}

时间复杂度: O(N),其中N指的是数组nums的大小。分析与方法一相同。
空间复杂度: O(1),输出数组不算进空间复杂度中,因此我们只需要常数的空间存放变量。

【3】本题的难点在于不能使用除法 ,即需要只用乘法生成数组 ans。根据题目对ans[i]的定义,可列出下图所示的表格。

根据表格的主对角线(全为1),可将表格分为上三角下三角两部分。分别迭代计算下三角和上三角两部分的乘积,即可 不使用除法 就获得结果。

下图中A=nums, B=ans
在这里插入图片描述
算法流程:
初始化: 数组ans,其中ans[0]=1;辅助变量tmp=1
计算ans[i]下三角各元素的乘积,直接乘入ans[i]
计算ans[i]上三角各元素的乘积,记为tmp,并乘入ans[i]
返回ans

class Solution {//假如nums为[1,2,3,4],那么answer的值分别为[(2,3,4),(1,3,4),(1,2,4),(1,2,3)]//如果吧i当前值相乘的时候看做是1那么就有如下样式//  1, 2, 3, 4 //  1, 1, 3, 4//  1, 2, 1, 4//  1, 2, 3, 1// 他的对角线1将他们分割成了两个三角形,对于answer的元素,//我们可以先计算一个三角形每行的乘积,然后再去计算另外一个三角形每行的乘积,//然后各行相乘,就是answer每个对应的元素public int[] productExceptSelf(int[] nums) {int length = nums.length;//先初始化一个answer数组,但是很多解答都没说明的是这个answer数组,//并不是以此计算就得出的结果,而是两次乘积之后的结果int[] answer = new int[length];//初始化一个初始值,作为三角乘积计算的开始answer[0] = 1;//先计算左边三角的乘积for(int i = 1; i < length; i++){answer[i] = answer[i-1] * nums[i-1];}//再次计算右边三角形,为什么是length-2呢?//length-1是最后一个值的索引,但是最后一个值temp[length-1] = 1,//也是对应对角线上的1,所以不在进行相乘处理//temp的作用是计算右边三角形的乘积的累计值,然后再和answer相乘,//注意!!!:不能直接nums[i+1]相乘那会在计算右三角的时候变成每行乘积与nums[i+1]的错误答案int temp = 1;for(int i = length - 2; i >= 0; i--){//先将每行乘积赋予一个中间值temp *= nums[i+1];answer[i] *= temp;}return answer;}
}

时间复杂度O(N) 其中N为数组长度,两轮遍历数组nums,使用 O(N)时间。
空间复杂度O(1) 变量tmp使用常数大小额外空间(数组ans作为返回值,不计入复杂度考虑)。

原数组:       [1       2       3       4]
左部分的乘积:   1       1      1*2    1*2*3
右部分的乘积: 2*3*4    3*4      4      1
结果:        1*2*3*4  1*3*4   1*2*4  1*2*3*1

从上面的图可以看出,当前位置的结果就是它左部分的乘积再乘以它右部分的乘积。因此需要进行两次遍历,第一次遍历用于求左部分的乘积,第二次遍历在求右部分的乘积的同时,再将最后的计算结果一起求出来。

【4】不准用除法,那我就用右移运算。先求出整个数组的乘积。然后利用极限的思想,用右移运算符,配合加法累算,得出总乘积是数组中每个元素的倍数。

咱们不用除法,但是需要用一点微积分知识。

class Solution {
public:int compute(int sum,int val){if(val==1) return sum;int k=0,cnt;long long tmp; while(sum>0){cnt=0;tmp=val;while(tmp<<1<sum){cnt++;tmp<<=1;}sum-=tmp;k+=1<<cnt;}return k;}vector<int> productExceptSelf(vector<int>& nums){int n=nums.size(),k;int idx=1,cnt=0;int sum,val;for(auto v:nums){if(v==0){cnt++;if(cnt==2) break;}else idx*=v;}if(cnt>0){for(auto& v:nums){if(cnt==1&&v==0)v=idx;else v=0;}return nums;}for(auto& v:nums){sum=abs(idx);val=abs(v);k=compute(sum,val);if(idx<0&&v<0||idx>0&&v>0)v=k;else v=k*-1;}return nums;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【SQL】SQL常见面试题总结(2)

目录 1、增删改操作1.1、插入记录&#xff08;一&#xff09;1.2、插入记录&#xff08;二&#xff09;1.3、插入记录&#xff08;三&#xff09;1.4、更新记录&#xff08;一&#xff09;1.5、更新记录&#xff08;二&#xff09;1.6、删除记录&#xff08;一&#xff09;1.7、…

Spring初学入门(跟学笔记)

一、Spring概述 Spring是一款主流的Java EE轻量级开源框架。 Spring的核心模块&#xff1a;IoC&#xff08;控制反转&#xff0c;指把创建对象过程交给Spring管理 &#xff09;、AOP&#xff08;面向切面编程&#xff0c;在不修改源代码的基础上增强代码功能&#xff09; 二、…

常用五款文件加密软件|好用加密软件工具分享

随着信息化时代的到来&#xff0c;数据安全问题日益凸显&#xff0c;加密软件应运而生&#xff0c;成为了保护数据安全的重要手段。在市场上&#xff0c;众多加密软件层出不穷&#xff0c;各有千秋。本文将介绍几款常用的加密软件&#xff0c;分析它们的优缺点&#xff0c;以帮…

使用JasperReport工具,生成报表模版,及通过JavaBean传参,常见问题及建议

1.下载JasperReport工具 下载地址:社区版 - Jaspersoft 社区 邮箱:lorettepatri.ckoa5434gmail.com 密码:Zx123456. 2.工具使用方法注意 1.一次参数需要在左下角Parameters中新建,直接拖转右上角的TextField不会自动新建参数,到头来还是要在Parameters中新建 2.循环参数需…

Kexp 动态展示 k8s 资源对象依赖关系

kexp[1] 旨在以可视化的方式帮助用户理解和探索 Kubernetes 的能力。 适用场景&#xff1a; 学习和探索 Kubernetes 的功能。 应用开发&#xff0c;提供每个应用的对象图预设。 控制器和操作器的开发&#xff0c;支持动态对象图。 即将推出类似 Postman 的 Kubernetes API …

如何组织 Vue 项目

介绍 在启动 Vue 项目时&#xff0c;思考项目结构至关重要。主要考虑因素是预期项目的规模。在本篇博文中&#xff0c;我将探讨适用于不同规模 Vue 项目的各种结构。这个考虑与康威定律相吻合&#xff1a; “设计系统的组织受限于产生这些组织沟通结构的设计。” - 梅尔康威 基…

linux防火墙的操作

linux防火墙的操作 前言1查看防火墙状态2暂时关闭防火墙3永久关闭防火墙4开启防火墙5开启指定端口6关闭指定端口7立即生效8查看开放的端口 前言 systemctl是管理linux中服务的命令&#xff0c;可以对服务进行启动、停止、重启、查看状态等操作 firewall-cmd是linux中专门用于控…

shell脚本之sort,uniq,tr,cut,sphit,paste,ecal与正则表达式

sort命令 uniq命令 tr命令 cut命令 sphit命令 paste命令 ecal命令 正则表达式 sort命令 sort命令---以行为单位对文件内容进行排序&#xff0c;也可以根据不同的数据类型来排序 比较原则是从首字符向后&#xff0c;依次按ASCII码值进行比较&#xff0c;最后将他们按升序…

Centos7使用kubeadm搭建k8s集群(一主两从)----(mac版)

一、环境准备 1、下载centos7镜像 阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区 下载地址: centos安装包下载_开源镜像站-阿里云 选择对应的版本即可&#xff0c;我下载的&#xff1a;CentOS-7-x86_64-DVD-2207-02.iso 2、使用VirtualBox安装centos 选择新建&#xff0c…

集成了Gemini的Android Studio,如虎添翼

今天将Android Studio升级到最新版&#xff08;Jellyfish&#xff09;。发现在new features中有一条&#xff1a; Code suggestions with Gemini in Android Studio 打开路径为&#xff1a; View > Tool Windows > Gemini 支持多国语言&#xff0c;英文、中文都能正确理解…

C# 快速排序(QuickSort)

QuickSort是一种基于分而治之算法的排序算法&#xff0c;它选择一个元素作为主元&#xff0c;并通过将主元放置在已排序数组中的正确位置&#xff0c;围绕所选主元对给定数组进行分区。 快速排序是如何工作的&#xff1f; QuickSort中的关键过程是partition()。分区的…

二手手机行业商家如何利用二手机店erp进行破局?

在数字化和AI发展越发先进的的今天&#xff0c;二手手机市场正迎来前所未有的变革。途渡科技精心打造的超机购ERP管理软件&#xff0c;凭借其独特的智能化、高效化特点&#xff0c;正在引领这场变革&#xff0c;为二手手机商家提供全面、深度的数字化管理解决方案。二手手机商家…

【FFmpeg】Filter 过滤器 ② ( 裁剪过滤器 Crop Filter | 裁剪过滤器语法 | 裁剪过滤器内置变量 | 裁剪过滤器常用用法 )

文章目录 一、裁剪过滤器1、裁剪过滤器简介2、裁剪过滤器语法3、裁剪过滤器内置变量4、裁剪过滤器示例5、裁剪过滤器应用6、裁剪过滤器图示 二、裁剪过滤器常用用法1、裁剪指定像素的视频区域2、裁剪视频区域中心正方形 - 默认裁剪3、裁剪视频区域中心正方形 - 手动计算4、裁剪…

Postman历史版本安装与runner测试

前言 实际上就是笔者本地做demo&#xff0c;postman使用了最新版本&#xff0c;本身也没问题&#xff0c;不过postman不支持不登录做runner测试了&#xff0c;很多功能必须登录账号才能使用&#xff0c;否则只能使用http工具发送的能力&#xff0c;而postman本身就是一个简单工…

每周题解:牛的旅行

题目描述 牛的旅行 农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言&#xff0c;你能看到至少有两个牧区不连通。 现在&#xff0c;John想在农场里添加一条路径 ( 注意&#xff0c;恰好一条 )。对这条路径有这样的…

nuget局域网在线包制作,nuget打包,nuget打自己的包

目录 首先编辑类库项目的.csproj文件信息 打包项目 设置局域网nuget包 Nuget包管理器--->程序包源 微软帮助文档&#xff1a; NuGet 及其功能介绍 | Microsoft Learn https://learn.microsoft.com/zh-cn/nuget/what-is-nuget 承载自己的 NuGet 源 https://learn.mic…

Python 小抄

Python 备忘单 目录 1.语法和空格 2.注释 3.数字和运算 4.字符串处理 5.列表、元组和字典 6.JSON 7.循环 8.文件处理 9.函数 10.处理日期时间 11.NumPy 12.Pandas 要运行单元格&#xff0c;请按 ShiftEnter 或单击页面顶部的 Run&#xff08;运行&#xff09;。 1.语法和空格…

垃圾分类管理系统java项目

文章目录 垃圾分类管理系统一、项目演示二、项目介绍三、系统部分功能截图四、部分代码展示五、底部获取项目&#xff08;9.9&#xffe5;带走&#xff09; 垃圾分类管理系统 一、项目演示 垃圾分类管理系统 二、项目介绍 系统角色&#xff1a;管理员、用户 1、登录、注册功能…

析构函数详解

目录 析构函数概念特性对象的销毁顺序 感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接 &#x1f412;&#x1f412;&#x1f412; 个人主页 &#x1f978;&#x1f978;&#x1f978; C语言 &#x1f43f;️&#x1f43f;️&#x1f43f;️ C语言例题 &…

2024042002-计算机网络 - 应用层

计算机网络 - 应用层 计算机网络 - 应用层 域名系统文件传送协议动态主机配置协议远程登录协议电子邮件协议 1. SMTP2. POP33. IMAP 常用端口Web 页面请求过程 1. DHCP 配置主机信息2. ARP 解析 MAC 地址3. DNS 解析域名4. HTTP 请求页面 域名系统 DNS 是一个分布式数据库&…