当前位置: 首页 > news >正文

除自身以外数组的乘积(c语言详解)

题目:除自身外数组的乘积

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

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

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

提示:

 2 <= nums.lengh <= 10^5

-30 <= nums[i] <= 30

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

示例 1:

输入:nums=[ 1,2,3,4 ]

输出:[ 24,12,8,6 ]

示例 2:

输入:nums=[ -1,-1,0,-3,3 ]

输出:[ 0,0,9,0,0 ]

解题思路:

定义两个数组(前缀乘积数组与后缀乘积数组),前缀数组为:left [ ] ,后缀数组:right [ ] ;

left [ i ] 里存 nums [ i ] 前面的乘积和,righ[ i ] 里存 nums [ i ] 后面的乘积和,(为空时存1);

创建一个动态内存变量 int* ret=(int*)malloc(sizeof(int)*numsSize);

然后ret [ i ]=left [ i ] * right [ i ],存储后返回;

思路实现:

因为数组元素 2 <= nums.lengh <= 10^5

所以前缀和后缀数组申请的数组大小都是10^5;

int left[100000]={0};
int right[100000]={0};

然后就是遍历求前缀乘积数组的各项值:

    //前缀乘积和for(i=0;i<numsSize;i++){if(i==0){left[i]=1;}else{left[i]=left[i-1]*nums[i-1];}}

解析:

这里呢用数组 nums [ 1,2,3,4,5,6 ] 来举例; 

此时,left [ 0 ] =1,然后 left [ 1 ] = left [ 0 ] * nums [ 0 ]  相当于 left [ 1 ] = nums [ 0 ] ;

left [ 2 ] = left [ 1 ] * nums [ 1 ]  相当于 left [ 2 ] = nums [ 0 ] * nums [ 1 ] ;

left [ 3 ] = left [ 2 ] * nums [ 2 ]  相当于 left [ 3 ] = nums [ 0 ] * nums [ 1 ] * nums [ 2 ] ;

。。。。。。

left [ 5 ] = left [ 4 ] * nums [ 4 ]  相当于 left [ 5 ] = nums [ 0 ] * nums [ 1 ] * nums [ 2 ] * nums [ 3 ] * nums [ 4 ] ;

想必大家也已经找到其中的规律了;

然后就是遍历求后缀乘积数组的各项值:

   //后缀乘积和for(i=numsSize-1;i>=0;i--){if(i==numsSize-1){right[i]=1;}else{right[i]=right[i+1]*nums[i+1];}}

解析:

同理:nums [ 1,2,3,4,5,6 ]

left [ 5 ] =1,然后 left [ 4 ] = left [ 5 ] * nums [ 5 ]  相当于 left [ 4 ] = nums [ 5 ] ;

left [ 3 ] = left [ 4 ] * nums [ 4 ]  相当于 left [ 3 ] = nums [ 4 ] * nums [ 5 ] ;

left [ 2 ] = left [ 3 ] * nums [ 3 ]  相当于 left [ 2 ] = nums [ 3 ] * nums [ 4 ] * nums [ 5 ] ;

。。。。。。

left [ 0 ] = left [ 1 ] * nums [ 1 ]  相当于 left [ 0 ] = nums [ 1 ] * nums [ 2 ] * nums [ 3 ] * nums [ 4 ] * nums [ 5 ] ;

然后就是给返回值(* returnSize)赋值,以及创建动态内(ret),以及给其赋值再返回;

    * returnSize=numsSize;int* ret=(int*)malloc(4*numsSize);//给返回指针赋值for(i=0;i<numsSize;i++){ret[i]=left[i]*right[i];}

时间复杂度为(O(N) ) ;

这就是这道题目的基本思路,下面是程序源代码:

int* productExceptSelf(int* nums, int numsSize, int* returnSize){int i=0;int left[100000]={0};int right[100000]={0};//前缀乘积和for(i=0;i<numsSize;i++){if(i==0){left[i]=1;}else{left[i]=left[i-1]*nums[i-1];}}//后缀乘积和for(i=numsSize-1;i>=0;i--){if(i==numsSize-1){right[i]=1;}else{right[i]=right[i+1]*nums[i+1];}}* returnSize=numsSize;int* ret=(int*)malloc(4*numsSize);//给返回指针赋值for(i=0;i<numsSize;i++){ret[i]=left[i]*right[i];}return ret;
}

如有不足欢迎来补充交流!

完结。。


        

相关文章:

除自身以外数组的乘积(c语言详解)

题目&#xff1a;除自身外数组的乘积 给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请不要使用除…...

ONES × 鲁邦通|打造研发一体化平台,落地组织级流程规范

近日&#xff0c;ONES 签约工业互联网行业领先的解决方案提供商——鲁邦通&#xff0c;助力鲁邦通优化组织级流程规范&#xff0c;落地从需求到交付的全生命周期线上化管理。 依托于 ONES 一站式研发管理平台&#xff0c;鲁邦通在软硬件设计开发、项目管理和精益生产等方面的数…...

【GaussDB】 SQL 篇

建表语句 表的分类 普通的建表语句 复制表内容 只复制表结构 create table 新表名(like 源表名 including all); 如果希望注释被复制的话要指定including comments 复制索引、主键约束和唯一约束&#xff0c;那么需要指定including indexes including constraints &#xf…...

rn和flutter出现“Running Gradle task ‘assembleDebug

在第一次运行rn和flutter时&#xff0c;会卡在Running Gradle task assembleDebug&#xff0c;可以使用阿里的镜像&#xff0c;如下图&#xff1a; maven { url https://maven.aliyun.com/repository/google/ } google() maven { url https://maven.aliyun.com/repository/jcen…...

Shell脚本基础( 四: sed编辑器)

目录 1 简介 1.1 sed编辑器的工作流程 2 sed 2.1 基本用法 2.2 sed基本格式 2.2.1 sed支持正则表达式 2.2.2 匹配正则表达式 2.2.3 奇数偶数表示 2.2.4 -d选项删除 2.2.5 -i修改文件内容 2.2.6 -a 追加 2.3 搜索替代 2.4 变量 1 简介 sed是一种流编辑器&#xff0c;…...

微信消息没通知iphone can‘t show notifications

小虎最近手机微信消息没通知&#xff0c;本来以为要卸载&#xff0c;但是发现原来是多客户端登录导致消息被其他平台截取&#xff0c;所有没有通知。 解决方法 小虎是在手机和电脑端同时登录的&#xff0c;所有退出电脑端后手机新消息就有提示了。可能是一个bug。...

Linux Kernel:pid与namespace

环境: Kernel Version:Linux-5.10 ARCH:ARM64 一:前言 Linux内核涉及进程和程序的所有算法都围绕task_struct数据结构建立,具体可看另一篇文章: Linux Kernel:thread_info与task_struct 同时Linux提供了资源限制(resource limit, rlimit)机制,对进程使用系统资源施…...

开源后台管理系统Geekplus Admin

本系统采用前后端分离开发模式&#xff0c;后端采用springboot开发技术栈&#xff0c;mybatis持久层框架&#xff0c;redis缓存&#xff0c;shiro认证授权框架&#xff0c;freemarker模版在线生成代码&#xff0c;websocket消息推送等&#xff0c;后台管理包含用户管理&#xf…...

【MATLAB基础绘图第16棒】绘制热图(Heatmap)

热图&#xff08;Heatmap&#xff09; 热图的主要作用是直观展示重点研究对象的差异情况&#xff0c;多用于经济学与工学差异性分析之中。 heatmap函数创建热图 语法 hheatmap(tbl,xvar,yvar) hheatmap(tbl,xvar,yvar,ColorVariable,cvar) hheatmap(cdata) hheatmap(xvalue…...

数据库--SQL关键字的执行顺序

数据库相关链接&#xff1a; 数据库--数据类型&#xff1a;http://t.csdn.cn/RtqMD 数据库--三大范式、多表查询、函数sql&#xff1a;http://t.csdn.cn/udJSG 数据库--MySQL增删改查&#xff1a;http://t.csdn.cn/xkiti 一、一条sql语句通常包括&#xff1a; select fro…...

如何优雅地处理Java多线程编程中的共享资源问题,以确保线程安全和高性能?

文章目录 &#x1f389;欢迎来到Java面试技巧专栏~如何优雅地处理Java多线程编程中的共享资源问题&#xff1f; ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&#xff1a;IT陈寒的博客&#x1f388;该系列文章专栏&#xff1a;Java面试技巧文章作者技术和水平有限&…...

每天一道leetcode:剑指 Offer 64. 求1+2+…+n(中等递归)

今日份题目&#xff1a; 求 12...n &#xff0c;要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句&#xff08;A?B:C&#xff09;。 示例1 输入: n 3 输出: 6 示例2 输入: n 9 输出: 45 提示 1 < n < 10000 题目思路 使用递归…...

服务器安装centos7踩坑

1、制作启动工具 下载iso https://developer.aliyun.com/mirror/?spma2c6h.25603864.0.0.20387abbo2RFbn http://mirrors.aliyun.com/centos/7.9.2009/isos/x86_64/?spma2c6h.25603864.0.0.1995f5ad4AhJaW下载 UltraISO https://cn.ultraiso.net/插入u盘启动 到了如图所示页面…...

Java | IDEA中 jconsole 不是内部或外部命令,也不是可运行的程序

解决办法&#xff1a; 1.先将Terminal的Shell path 修改为C:\WINDOWS\system32\cmd.exe 2.在检查环境变量中的ComSpec的值 3.找到自己电脑下载的jdk的bin的地址 4.将jdk的bin地址加入到系统变量path中...

将Swift Package构建为通用二进制文件 Universal Binary

将Swift软件包构建为通用二进制文件 因此&#xff0c;在苹果在WWDC 2020期间宣布他们将把Mac从英特尔处理器过渡到苹果硅之后&#xff0c;现在是时候让每个人都准备好他们的软件了。 对大多数人来说&#xff0c;这次过渡可能更容易一些&#xff0c;特别是那些已经在iOS上支持a…...

正则表达式:贪婪与非贪婪模式

正则中的三种模式&#xff0c;贪婪匹配、非贪婪匹配和独占模式。 在这 6 种元字符中&#xff0c;我们可以用 {m,n} 来表示 &#xff08;*&#xff09;&#xff08;&#xff09;&#xff08;?&#xff09; 这 3 种元字符&#xff1a; 贪婪模式&#xff0c;简单说就是尽可能进行…...

UVa247 Calling Circles(Floyd warshall算法)

题意 给定两个人相互打电话&#xff0c;如果a打给b,b打给c,c打给a&#xff0c;则说a,b,c在同一电话圈中。给出n个人的m次通话&#xff0c;输出所有的电话圈 思路 用graph[u][v]1表示u和v之间有打电话。在使用floyd算法计算所有的点对之间的值。graph[u][v]1表示u,v之间有直接…...

Java项目之基于ssm框架的社区生活超市管理系统(附源码)

基于ssm框架的社区生活超市管理系统设计与实现&#xff08;程序源码毕业论文&#xff09; 大家好&#xff0c;今天给大家介绍基于ssm框架的社区生活超市管理系统设计与实现&#xff0c;本论文只截取部分文章重点&#xff0c;文章末尾附有本毕业设计完整源码及论文的获取方式。更…...

Android 实现录音功能

思路&#xff1a; 通过媒体录制器MediaRecorder实现&#xff1a;MediaRecorder是Android自带的音频和视频录制工具&#xff0c;它通过操纵摄像头和麦克风完成媒体录制&#xff0c;既可录制视频&#xff0c;又可单独录制音频。 MediaRecorder常用方法(录音与录像通用)&#xf…...

drawio导出矢量图

1.选中要导出的图 2.导出为pdf 3.用adobe打开pdf&#xff0c;另存为eps...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...