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

2024-01-14 20:44

本文主要是介绍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:除自身以外数组的乘积的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/606456

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };

PHP7扩展开发之数组处理

前言 这次,我们将演示如何在PHP扩展中如何对数组进行处理。要实现的PHP代码如下: <?phpfunction array_concat ($arr, $prefix) {foreach($arr as $key => $val) {if (isset($prefix[$key]) && is_string($val) && is_string($prefix[$key])) {$arr[

Go 数组赋值问题

package mainimport "fmt"type Student struct {Name stringAge int}func main() {data := make(map[string]*Student)list := []Student{{Name:"a",Age:1},{Name:"b",Age:2},{Name:"c",Age:3},}// 错误 都指向了最后一个v// a

码蹄集部分题目(2024OJ赛9.4-9.8;线段树+树状数组)

1🐋🐋配对最小值(王者;树状数组) 时间限制:1秒 占用内存:64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que

【第0006页 · 数组】寻找重复数

【前言】本文以及之后的一些题解都会陆续整理到目录中,若想了解全部题解整理,请看这里: 第0006页 · 寻找重复数         今天想讨论的一道题在 LeetCode 上评论也是颇为“不错”。有一说一,是道好题,不过我们还是得先理解了它才算真正的好题。这里我们展示一种使用二进制的做法,希望能帮到你哟! 【寻找重复数】给定一个包含 n + 1 个整数的数组 nums ,其数字都