/**
* Implement a method which takes an integer array and returns an integer array (of equal size) in
* which each element is the product of every number in the input array with the exception of the
* number at that index.
*
* Example:
* [3, 1, 4, 2] => [8, 24, 6, 12]
*/
public int[] selfExcludingProduct(int[] input) {
// implementation...
}
Click here for original problem.Update 2016-10-05
A neater solution. Go through the array twice. First time get the product of all numbers previous to current number, second time get products after current number.
public int[] productExceptSelf(int[] nums) { int len = nums.length; int[] rst = new int[len]; if (len == 0) { return rst; } rst[0] = 1; for (int i = 1; i < len; i++) { rst[i] = rst[i - 1] * nums[i - 1]; } int p = nums[len - 1]; for (int i = len - 2; i >= 0; i--) { rst[i] *= p; p *= nums[i]; } return rst; }
public class SelfExcludingProduct { public int[] selfExcludingProduct (int[] input) { if (input == null) throw new NullPointerException ("Null input array!"); int[] productArray = new int[input.length]; if (input.length == 0) return productArray; int product = 1; int numOfZeros = 0; for (int i = 0; i < input.length; i++) { if (input[i] != 0) product *= input[i]; else numOfZeros++; if (numOfZeros >= 2) { return productArray; } } for (int i = 0; i < input.length; i++) { if (numOfZeros == 0) { productArray[i] = product / input[i]; } else { if (input[i] == 0) productArray[i] = product; else productArray[i] = 0; } } return productArray; } }
No comments:
Post a Comment