Java构建乘积数组的方法

2024-10-23 22:07:20

本文实例为大家分享了Java构建乘积数组的具体实现代码，供大家参考，具体内容如下

给定一个数组A[0,1,…,n-1]，请构建一个数组B[0,1,…,n-1]，其中B中的元素B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]。

不能使用除法。

代码

解法一

暴力法，这是本能就能想到的解决办法。

public static int[] multiply(int[] array) {
 if (array == null) {
 return null;
 }
 int len = array.length;
 if (len == 0) {
 return null;
 }
 int[] result = new int[len];
 for (int i = 0; i < len; i++) {
 int multiply = 1;
 for (int j = 0; j < len; j++) {
  if (j != i) {
  multiply *= array[j];
  }
 }
 result[i] = multiply;
 }
 return result;
 }

解法二

从中可以看出通过数组A计算数组B的时候，红色部分不参与乘积的计算，以红色部分做分割，可以看错是红色左边部分的乘积与红色右边部分乘积的乘积

所以此时先根据数组A把对应左边部分的乘积和右边部分的乘积分别计算出来得到两个新的数组，即LEFT和RIGHT

这样可以得到公式：B[i]=LEFT[i]*RIGHT[i]，如下所示

对于B[0]，因为没有左边部分，可以认为是1*RIGHT[0]
如果B[n-1]，没有右边部分，所以认为是LEFT[n-1]*1

以下是代码实现

public static int[] multiply2(int[] array) {
 if (array == null) {
 return null;
 }
 int len = array.length;
 if (len == 0) {
 return null;
 }
 int[] left = new int[len];
 int[] right = new int[len];
 int[] result = new int[len];
 // 数组B中第一个数字没有左边部分，所以左边乘积数组第一个数字是1
 left[0] = 1;
 // 计算B[i]对应的在A中的左边部分的乘积，数组A从前向后计算
 for (int i = 1; i < len; i++) {
 // 因为要B[i]不需要计算A[i]，所以左边部分的乘积计算其实需要的是A中对应下标i的上一个下标及之前的数字
 left[i] = left[i - 1] * array[i - 1];
 }
 // 数组B中最后一个数字没有右边部分，所以右边乘积数组的最后一个数字是1
 right[len - 1] = 1;
 // 计算B[i]对应的在A中的右边部分的乘积，数组A从后向前计算，这样才可以一次遍历完
 // 因为计算可以用到上一次的结果，即上一次的结果*本次下标的值
 for (int i = len - 1; i > 0 ; i--) {
 // 因为要B[i]不需要计算A[i]，所以右边部分的乘积计算其实需要的是A中对应下标i的下一个下标及之后的数字
 right[i - 1] = right[i] * array[i];
 }
 for (int i = 0; i < len; i++) {
 result[i] = left[i] * right[i];
 }
 return result;
 }

 public static void main(String[] args) {
 int[] array = {1, 2, 3, 4};
 int[] result = multiply2(array);
 for (Integer i : result) {
 System.out.print(i + " ");
 }

}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

java实现左旋转字符串

汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果.对于一个给定的字符序列S,请你把其循环左移K位后的序列输出.例如,字符序列S="abcXYZdef",要求输出循环左移3位后的结果,即"XYZdefabc".是不是很简单?OK,搞定它! 代码解法一最直观的方式,依次将需要移位的字符移动至最后,但是每个字符都需要移动数组的长度-1,如果数组的长度是n,需要移k位,则总共需要移动 k * (n - 1) publ
理解 Java 核心基础精髓解析

1.字符串不变性下面这张图展示了这段代码做了什么 String s = "abcd"; s = s.concat("ef"); 2.equals() 方法与 hashCode() 方法的区别 HashCode 被设计用来提高性能.equals() 方法与 hashCode() 方法的区别在于: 如果两个对象相等(equal),那么他们一定有相同的哈希值. 如果两个对象的哈希值相同,但他们未必相等(equal). 3.Java异常类的层次结构图中红色部分为受检查异
java中线程的状态学习笔记

java开发中,我们经常会遇到线程的问题,比如你做一个商城,就需要考虑它的并发问题等等,今天给大家分享一下java中线程的状态先说线程的第一个状态,是新建状态,这个是线程刚刚创建的时候,如: new Thread(),具体如图线程的第二种状态是可执行状态,就是调用了start方法后的状态,当然了,一个运行的状态,他有可能是正在运行的,也有可能是没有运行的,只是他的状态是可运行的状态,具体如图第三种状态是被阻塞或者处于等待的线程,处于这种状态下的线程是不活动且不运行的,比如说调用了wait方
java简单实现数组中的逆序对

题目描述: 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对.输入一个数组,求出这个数组中的逆序对的总数P.并将P对1000000007取模的结果输出. 即输出P%1000000007 解题思路: 一开始一头雾水,后面想到了使用归并排序的思想,其实有多少个逆序对,就是归并排序的时候,后面的数要超越前面多少个,嗯,好像不是很好说,要不然直接看代码吧.还要注意,题目当中说要输出取模的结果,这说明数据可能非常大,所以如果只是单纯的在最后取模的话可能还是无法避免数据太大的影
java实现翻转单词顺序列

本文实例为大家分享了java实现翻转单词顺序列的具体代码,供大家参考,具体内容如下最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上.同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思.例如,"student. a am I".后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是"I am a student.".Cat对一一的翻转这些单词顺序可不在行,你能帮助他么? 代码借助上一篇文章左旋
java.util.Collection源码分析与深度理解

写在开头 java.util.Collection 作为Java开发最常用的接口之一,我们经常使用,今天我带大家一起研究一下Collection接口,希望对大家以后的编程以及系统设计能有所帮助,本文所研究的jdk版本为jdk1.8.0_131 明确一下几点: Collection是接口,其继承了Iterable接口 Collection属于单值类型集合,重点子接口List接口和Set接口 Java.util.List接口(有序.不唯一) ArraryList ArrayList 是一个数组队列,
Java构建乘积数组的方法

本文实例为大家分享了Java构建乘积数组的具体实现代码,供大家参考,具体内容如下给定一个数组A[0,1,-,n-1],请构建一个数组B[0,1,-,n-1],其中B中的元素B[i]=A[0]A[1]-A[i-1]*A[i+1]-*A[n-1]. 不能使用除法. 代码解法一暴力法,这是本能就能想到的解决办法. public static int[] multiply(int[] array) { if (array == null) { return null; } int len = ar
Java构建高效结果缓存方法示例

缓存是现代应用服务器中非常常用的组件.除了第三方缓存以外,我们通常也需要在java中构建内部使用的缓存.那么怎么才能构建一个高效的缓存呢? 本文将会一步步的进行揭秘. 使用HashMap 缓存通常的用法就是构建一个内存中使用的Map,在做一个长时间的操作比如计算之前,先在Map中查询一下计算的结果是否存在,如果不存在的话再执行计算操作. 我们定义了一个代表计算的接口: public interface Calculator<A, V> { V calculate(A arg) throws I
php实现构建排除当前元素的乘积数组方法

构建乘积数组给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1].不能使用除法. 这题的意思是 B数组的元素是A数组中所有元素的乘积,但是要排除掉当前元素 A数组在i元素左右分成两部分,分别相乘 left数组是 A[0]...A[n-1], right数组是A[1]...A[n] 组合出新的数组 $A=array(1,2,3,4); multiply($A);
C语言构建动态数组完整实例

本文以一个完整的实例代码简述了C语言构建动态数组的方法,供大家参考,完整实例如下: #include <stdio.h> #include <malloc.h> int main(void) { int len; int * arr; printf("请输入数组长度:"); scanf("%d", &len); arr = (int *)malloc(sizeof(int)*len); printf("请输入数组的值:&qu
java 两个数组合并的几种方法

本文介绍了java 两个数组合并的几种方法,分享给大家,也给自己留个笔记需求:两个字符串合并(如果想去重复,参考下一篇--数组去重复及记录重复个数) //方法一 Arrays类 String[] a = {"A","B","C"}; String[] b = {"D","E"}; // List<String> list = Arrays.asList(a); --OK // List<
java数据结构与算法之双向循环队列的数组实现方法

本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p
实例讲解Java编程中数组反射的使用方法

什么是反射 "反射(Reflection)能够让运行于JVM中的程序检测和修改运行时的行为."这个概念常常会和内省(Introspection)混淆,以下是这两个术语在Wikipedia中的解释: 内省用于在运行时检测某个对象的类型和其包含的属性: 反射用于在运行时检测和修改某个对象的结构及其行为. 从它们的定义可以看出,内省是反射的一个子集.有些语言支持内省,但并不支持反射,如C++. 内省示例:instanceof 运算符用于检测某个对象是否属于特定的类. if (obj inst
Java版C语言版简单使用静态语言实现动态数组的方法

动态语言相对于静态语言的一个优势,就是数组可以不需要预先确定大小,对于一些数组长度不确定的场景下是非常有用的.像PHP,只需要声明一下数组 $arr = array() 然后就可以直接 $arr[] = 1,$arr[] = 2,$arr[] = 3...这样一直加元素了,删除一个元素就直接使用unset($arr[1]),元素的空间就被释放了,而C和JAVA原生的数组就没有这么方便,声明的时候就必须先预先确定长度,由编译器分配相应的内存空间.不过通过一些巧妙的做法,也是可以实现一样的功能的,这
java String 转成Double二维数组的方法

WHY 朋友在群里求助一个问题,问题原型是这样的: String str = "{{10.14, 11.24, 44.55, 41.01},{12.10, 14.21, 52.14, 50.44},{14.44, 16.12, 45.42, 47.55}}"; 转成double[][]{ {10.14, 11.24, 44.55, 41.01}, {12.10, 14.21, 52.14, 50.44}, {14.44, 16.12, 45.42, 47.55} } 也就是把一个可以转
Java二维数组简单定义与使用方法示例

本文实例讲述了Java二维数组简单定义与使用方法.分享给大家供大家参考,具体如下: Java的二维数组是先创建一个一维数组,然后该数组的元素再引用另外一个一维数组.在使用二维数组的时候,通过两个中括号[]来访问每一层维度的引用,直到访问到最终的数据. public class MultiDimArray{ /** * @param args */ public static void main(String[] args) { int[][] arr = new int[3][]; arr[0]

Java构建乘积数组的方法

相关推荐

随机推荐