[算法]不包含本位置值的累乘数组

题目:

给定一个整型数组,返回不包含本位置的累乘数组。

例如:arr=[2,3,1,4],返回[12,8,24,6],即除自己外,其他位置的类乘。

要求:

1.时间复杂度为O(N).

2.除需要返回的结果数组之外,额外空间复杂度为O(1).

使用除法:

结果数组记为res,所有数的乘积记为all。如果数组中不含0,则设置res[i]=all/arr[i]。如果数组中有一个0,对唯一的arr[i]==0的位置令res[i]=all,其他位置都是0。如果数组中0的数量大于1,那么res所有位置上的值都是0。

	public static int[] product1(int[] arr) {
		if (arr == null || arr.length < 2) {
			return null;
		}
		int count = 0;
		int all = 1;
		for (int i = 0; i != arr.length; i++) {
			if (arr[i] != 0) {
				all *= arr[i];
			} else {
				count++;
			}
		}
		int[] res = new int[arr.length];
		if (count == 0) {
			for (int i = 0; i != arr.length; i++) {
				res[i] = all / arr[i];
			}
		}
		if (count == 1) {
			for (int i = 0; i != arr.length; i++) {
				if (arr[i] == 0) {
					res[i] = all;
				}
			}
		}
		return res;
	}

不使用除法:

1.生成两个长度和arr一样的新数组lr[]和rl[],lr[i]=arr[0…i],rl[i]=arr[i…N-1]。

2.res[i]=lr[i-1]*rl[i+1]

3.res[0]=rl[1],res[N-1]=lr[N-2]

这里又额外使用了两个数组,可以通过res数组复用的方式省略掉这两个数组,先把res数组作为辅助计算的数组,然后把res调整成结果数组返回。

	public static int[] product2(int[] arr) {
		if (arr == null || arr.length < 2) {
			return null;
		}
		int[] res = new int[arr.length];
		res[0] = arr[0];
		for (int i = 1; i < arr.length; i++) {
			res[i] = res[i - 1] * arr[i];
		}
		int tmp = 1;
		for (int i = arr.length - 1; i > 0; i--) {
			res[i] = res[i - 1] * tmp;
			tmp *= arr[i];
		}
		res[0] = tmp;
		return res;
	
时间: 02-12

[算法]不包含本位置值的累乘数组的相关文章

《程序员代码面试指南》第八章 数组和矩阵问题 不包含本位置值的累乘数组

题目 不包含本位置值的累乘数组 java代码 package com.lizhouwei.chapter8; /** * @Description: 不包含本位置值的累乘数组 * @Author: lizhouwei * @CreateDate: 2018/5/9 21:11 * @Modify by: * @ModifyDate: */ public class Chapter8_22 { public int[] product(int[] arr) { int[] res = new in

算法总结之 不包含本位置的累乘数组

给定一个整型数组arr,返回不包含本位置的乘数组 一般做法是用除法,新方法: 一个位置上 除去 自己值的累乘,就是自己左边的累乘再乘以自己右边的累乘,即 res[i]=lr[i-1]*rl[i+1] 最左的位置 和 最右的位置 比较特殊, 即 res[0]=rl[1] , res[N-1]=lr[N-2] 这样虽然可以得到结果,但是不好的是,用两个两个额外的数组,lr[]  rl[], 如何避免呢? 通过res数组复用的方式. 具体看代码吧: package TT; public class T

如何高效的检测一个数组是否包含某一个值

如何检测一个数组(未排序)是否包含一个指定的值?这在Java中是一个非常有用且常见的操作.这还是一个在stackoverflow投票最多的一个问题.在投票最多的答案中,有几种不同的方式来完成这个问题.但是时间复杂度存在很大的差异.下面,我将展示每个方法所花费的时间. 1.检测数组中是否包含某一个值的四种方式 1)使用List public static boolean useList(String[] arr, String targetValue) { return Arrays.asList

笔试算法题(22):二分法求旋转数组最小值 &amp; 骰子值概率

出题:将一个数组最开始的k个(K小于数组大小N)元素照搬到数组末尾,我们称之为数组的旋转:现在有一个已经排序的数组的一个旋转,要求输出旋转数组中的最小元素,且时间复杂度小于O(N): 分析: 时间复杂度小于O(N)也就是不能用常规的遍历思路:可以将数组看成两个都是递增序列(假设为升序)的子数组,并且前半段的元素均大于等于后半段的元素,分界点的位于后半段数组的第一个元素就是最小元素: 具体算法:两个指针left和right指向数组第一个和最后一个元素,使用Binary Search确定中间元素mi

【Stackoverflow好问题】java中,如何判断数组Array是否包含指定的值

问题 java中,如何判断数组Array是否包含指定的值 精华回答 1. Arrays.asList(...).contains(...) 2. 使用 Apache Commons Lang包中的ArrayUtils.contains String[] fieldsToInclude = { "id", "name", "location" }; if ( ArrayUtils.contains( fieldsToInclude, "i

js/jquery获取当前页面URL地址并判断URL字符串中是否包含某个具体值

js/jquery获取当前页面URL地址并判断URL字符串中是否包含某个具体值本文介绍jquery/js获取当前页面url地址的方法,在jquery与js中获取当前页面url方法是一样的,因为jquery没有自己相关的函数,使用js 的windows方法来获取,相关方法如下: window.location.pathname //设置或获取对象指定的文件名或路径 window.location.href //设置或获取整个 URL 为字符串 window.location.port //设置或获

使用E.W.D.Dijkstra设计算法实现算数表达式求值

要求:编程模拟(1+(2+3)*(4*5))的运算过程,重点在于如何解析由括号运算符和数字组成的字符串,并按照正确的顺序完成各种初级运算符的操作. 实现思路:用两个栈(LIFO)结构来实现(一个用于保存运算符,一个用于保存操作数) 将操作数压如操作数栈 将操作符压如操作符栈 忽略左括号 在遇到右括号时,弹出一个运算符,并弹出所需数量的操作数,并将操作符和操作数的运算结果压到操作数栈 1 package com.luochuang.demo.stdlib; 2 3 public class Eva

分期值、累计值的相互转换

-- 分期值到累计值代码示例1with temp00 as (select '2020-01-01' date1,1 num1union all select '2020-01-02' adate1,2 num1 union all select '2020-01-03' date1,3 num1union all select '2020-01-04' date1,4 num1 ) select t1.date1 new_date,sum(t2.num1) new_numfrom temp00

经典算法题每日演练——第十题 树状数组

原文:经典算法题每日演练--第十题 树状数组 有一种数据结构是神奇的,神秘的,它展现了位运算与数组结合的神奇魅力,太牛逼的,它就是树状数组,这种数据结构不是神人是发现不了的. 一:概序 假如我现在有个需求,就是要频繁的求数组的前n项和,并且存在着数组中某些数字的频繁修改,那么我们该如何实现这样的需求?当然大家可以往 真实项目上靠一靠. ① 传统方法:根据索引修改为O(1),但是求前n项和为O(n). ②空间换时间方法:我开一个数组sum[],sum[i]=a[1]+....+a[i],那么有点意