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

leetcode238:除自身以外数组的乘积

文章目录

  • 1.使用除法(违背题意)
  • 2.左右乘积列表
  • 3.空间复杂度为O(1)的方法

在leetcode上刷到了这一题,一开始并没有想到好的解题思路,写篇博客再来梳理一下吧。
在这里插入图片描述

在这里插入图片描述
题目要求:

  • 不使用除法
  • 在O(n)时间复杂度内

1.使用除法(违背题意)

该方法分以下几步:

  1. 先遍历数组,求数组所有元素的乘积sum
  2. 再遍历一遍数组,使用sum除以该下标对应的元素,将结果放在answer数组中

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int* answer = (int*)calloc(numsSize, sizeof(int));*returnSize = numsSize;int sum = 1;for (int i = 0; i < numsSize; i++){sum *= nums[i]; //求所有元素的乘积}for (int i = 0; i < numsSize; i++){answer[i] = sum / nums[i];}return answer;
}int main()
{int arr[] = { 1,2,3,4 };int sz = sizeof(arr) / sizeof(arr[0]);int count = 0;int* ret = productExceptSelf(arr, sz, &count);for (int i = 0; i < count; i++){printf("%d", *(ret + i));if (i != count - 1){printf(",");}}free(ret);ret = NULL;return 0;
}

2.左右乘积列表

相较于第一种方法,我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案,而是利用索引左侧所有数字的乘积和右侧所有数字的乘积(即前缀与后缀)相乘得到答案。这也是题目中暗示我们的
在这里插入图片描述

该方法分以下几步:

  • 初始化两个空数组 Left 和 Right。对于给定下标 i,Left[i] 代表的是 i 左侧所有数字的乘积,Right[i] 代表的是 i 右侧所有数字的乘积。
  • 对于数组 Left,Left[0] 应该是 1,因为第一个元素的左边没有元素。对于数组 Right,Right[length-1] 应为 1,因为最后一个元素右侧没有元素。(length 指的是输入数组的大小)
  • 对于其它的元素,Left[i] = Left[i-1] * nums[i-1] (i从1开始 i++)

在这里插入图片描述

  • 对于其它的元素,Right[i] = Right[i+1] * nums[i+1] (i从length-2开始 i–)

在这里插入图片描述

  • 当 Left 和 Right 数组填充完成,我们只需要在输入数组上迭代:answer[i] = Left[i] * Righti]
#include<stdio.h>
#include<stdlib.h>
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int* answer = (int*)calloc(numsSize, sizeof(int));*returnSize = numsSize;int Left[numsSize];int Right[numsSize];Left[0] = 1;Right[3] = 1;for (int i = 1; i < numsSize; i++){Left[i] = Left[i - 1] * nums[i - 1];}for (int i = 2; i >= 0; i--){Right[i] = Right[i + 1] * nums[i + 1];}for (int i = 0; i < numsSize; i++){answer[i] = Left[i] * Right[i];}return answer;
}int main()
{int arr[] = { 1,2,3,4 };int sz = sizeof(arr) / sizeof(arr[0]);int count = 0;int* ret = productExceptSelf(arr, sz, &count);for (int i = 0; i < count; i++){printf("%d", *(ret + i));if (i != count - 1){printf(",");}}free(ret);ret = NULL;return 0;
}

复杂度分析:

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

3.空间复杂度为O(1)的方法

由于输出数组不算在空间复杂度内,而且我们的answer数组只有最后才被用到,所以我们可以先将 Left 或 Right 数组用answer数组来计算。
该方法分为以下几步:

  • 先把answer数组当作 Left数组来计算,然后再动态构造 Right 数组得到结果。这样我们就节省了两个数组,空间复杂度就为O(1)了。
  • 动态构造Right数组我们只使用一个变量R就可以了,该变量初始化为1。R * nums[i] 即可得到最终的结果.

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int* answer = (int*)calloc(numsSize, sizeof(int));*returnSize = numsSize;int left[numsSize];int right[numsSize];answer[0] = 1;int R = 1;//先求前缀之积for (int i = 1; i < numsSize; i++){answer[i] = answer[i - 1] * nums[i - 1];}//求后缀之积与answerfor (int i = numsSize - 1; i >= 0; i--){// 对于下标 i,左边的乘积为 answer[i],右边的乘积为 Ranswer[i] = answer[i] * R;// R 需要包含右边所有的乘积,所以计算下一个结果时需要将当前值乘到 R 上R *= nums[i];}return answer;
}int main()
{int arr[] = { 1,2,3,4 };int sz = sizeof(arr) / sizeof(arr[0]);int count = 0;int* ret = productExceptSelf(arr, sz, &count);for (int i = 0; i < count; i++){printf("%d", *(ret + i));if (i != count - 1){printf(",");}}free(ret);ret = NULL;return 0;
}

复杂度分析

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

目前想到的方法就这些,后续想到会补充。

相关文章:

leetcode238:除自身以外数组的乘积

文章目录 1.使用除法&#xff08;违背题意&#xff09;2.左右乘积列表3.空间复杂度为O(1)的方法 在leetcode上刷到了这一题&#xff0c;一开始并没有想到好的解题思路&#xff0c;写篇博客再来梳理一下吧。 题目要求&#xff1a; 不使用除法在O(n)时间复杂度内 1.使用除法&am…...

VTK开发调试环境下载(VTK开发环境一步到位直接开发,无需自己配置编译 VS2017+Qt5.12.10+VTK)

一、无与伦比的优势 直接下载代码就可以调试的VTK代码仓库。 二、资源制作原理 这个资源根据VTK源码 编译出动态库文件 pdb lib dll 文件&#xff08; x64 debug &#xff09; 并将这两者同时放在一个代码仓库里&#xff0c;下载就能用。 三、使用方法&#xff08;vtk-so…...

【JAVA】在 Queue 中 poll()和 remove()有什么区别

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;JAVA ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 poll() 方法&#xff1a; remove() 方法&#xff1a; 区别总结&#xff1a; 结语 我的其他博客 前言 在Java的Queue接口中&…...

常用Java代码-Java中的Optional类和null安全编程

在Java中&#xff0c;Optional 是一个可以为null的容器对象。如果值存在则isPresent()方法返回true。调用get()方法会返回值&#xff0c;如果值为null则抛出NullPointerException。以下是一个详细的代码详解。 在之前的Java版本中&#xff0c;程序员需要手动检查是否为null&am…...

android.os.NetworkOnMainThreadException

问题 android.os.NetworkOnMainThreadException详细问题 核心代码如下&#xff1a; import android.os.Bundle;import androidx.appcompat.app.AppCompatActivity;import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja…...

Java生成四位数随机验证码

引言&#xff1a; 我们生活中登录的时候都要输入验证码&#xff0c;这些验证码是为了增加注册或者登录难度&#xff0c;减少被人用脚本疯狂登录注册导致的一系列危害&#xff0c;减少数据库的一些压力。 毕竟那些用脚本生成的账号都是垃圾账号 本次实践&#xff1a;生成这样的…...

编程探秘:Python深渊之旅-----数据可视化(八)

客户提出了对数据报告和图表的具体要求&#xff0c;这使得团队需要快速掌握数据可视化的技巧。派超决定深入了解 Python 中的数据可视化工具。 派超&#xff08;兴奋地&#xff09;&#xff1a;我们有机会做些真正酷炫的数据报告了&#xff01;我听说 Python 有很棒的图表库。…...

上海亚商投顾:创业板指冲高回落 光伏、航运股逆势走强

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 沪指1月12日冲高回落&#xff0c;创业板指午后跌近1%。北证50指数跌超6%&#xff0c;倍益康、华信永道、众诚科…...

Python3 中常用字符串函数介绍

介绍 Python 中有几个与 字符串数据类型相关的内置函数。这些函数让我们能够轻松修改和操作字符串。我们可以将函数视为在代码元素上执行的操作。内置函数是在 Python 编程语言中定义的&#xff0c;并且可以随时供我们使用的函数。 在本教程中&#xff0c;我们将介绍在 Pytho…...

Python - 深夜数据结构与算法之 AVL 树 红黑树

目录 一.引言 二.高级树的简介 1.树 2.二叉树 3.二叉搜索树 4.平衡二叉树 三.AVL 树 ◆ 插入节点 ◆ 左旋 ◆ 右旋 ◆ 左右旋 ◆ 右左旋 ◆ 一般形式 ◆ 实际操作 ◆ 总结 四.红黑树 ◆ 概念 ◆ 示例 ◆ 对比 五.总结 一.引言 前面我们介绍了二叉树、二叉…...

Zookeeper使用详解

介绍 ZooKeeper是一个分布式的&#xff0c;开放源码的分布式应用程序协调服务&#xff0c;是Google的Chubby一个开源的实现&#xff0c;是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件&#xff0c;提供的功能包括&#xff1a;配置维护、域名服务、分布…...

C#属性(Property)

文章目录 一、C#属性&#xff08;Property&#xff09;&#xff1f;二、属性的用法总结 一、C#属性&#xff08;Property&#xff09;&#xff1f; C#属性&#xff08;Property&#xff09;是一种访问器&#xff08;accessor&#xff09;&#xff0c;用于封装一个类的字段&…...

在docker中搭建部署clickhouse

因需要给网关日志拉取并存储供数据分析师分析&#xff0c;由于几十个项目的网关请求数量很大&#xff0c;放在mysql不合适&#xff0c;MongoDB不适合分析&#xff0c;于是准备存放在clickhouse&#xff0c;clickhouse对于读写支持也比较友好&#xff0c;说干就干 1、在服务器中…...

第九部分 使用函数 (三)

目录 一、文件名操作函数 1、dir 2、notdir 3、suffix 4、basename 5、addsuffix 6、addprefix 7、join 一、文件名操作函数 下面我们要介绍的函数主要是处理文件名的。每个函数的参数字符串都会被当做一个或是 一系列的文件名来对待。 1、dir $(dir <names..>…...

基础命令继续

1&#xff1a;创建目录命令 mkdir命令 注意&#xff1a;创建文件夹需要修改权限&#xff0c;请确保操作均在HOME目录内&#xff0c;不要在Home外操作&#xff0c;涉及到权限问题&#xff0c;HOME外无法识别 小结&#xff1a; 练习: 2&#xff1a;touch创建文件 2&#xff1a;c…...

uni-app做A-Z排序通讯录、索引列表

上图是效果图&#xff0c;三个问题 访问电话通讯录&#xff0c;拿数据拿到用户的联系人数组对象&#xff0c;之后根据A-Z排序根据字母索引快速搜索 首先说数据怎么拿 - 社区有指导https://ask.dcloud.net.cn/question/64117 uniapp 调取通讯录 // #ifdef APP-PLUSplus.contac…...

Codeforces Round 768 (Div. 1) D. Flipping Range(思维题 等价类性质 dp)

题目 思路来源 官方题解 洛谷题解 题解 可操作的最短区间长度肯定是gcd&#xff0c;记为g&#xff0c;然后考虑如何dp 考虑g个等价类&#xff0c;每个等价类i,ig,i2*g,... 每次翻转长度为g的区间&#xff0c;会同时影响到g个等价类总的翻转的奇偶性&#xff0c; 性质一&…...

springboot集成kafka消费数据

springboot集成kafka消费数据 文章目录 springboot集成kafka消费数据1.引入pom依赖2.添加配置文件2.1.添加KafkaConsumerConfig.java2.2.添加KafkaIotCustomProperties.java2.3.添加application.yml配置 3.消费者代码 1.引入pom依赖 <dependency><groupId>org.spri…...

单例模式---JAVA

目录 “饿汉”模式 完整代码 “懒汉”模式 完整代码 单例模式&#xff1a;保证某个类在程序中只存在唯一一份实例, 而不会创建出多个实例。 单例模式可以通过实例创建的时间来分为两种&#xff1a;“饿汉”和“懒汉”模式。 “饿汉”模式 所谓的“饿汉”模式实则就是在类…...

maven管理使用

maven基本使用 一、简介二、配置文件三、项目结构maven基本标签实践(例子) 四、pom插件配置五、热部署六、maven 外部手动加载jar打包方式Maven上传私服或者本地 一、简介 基于Ant 的构建工具,Ant 有的功能Maven 都有,额外添加了其他功能.本地仓库:计算机中一个文件夹,自己定义…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...