【LeetCode】238. Product of Array Except Self
LeetCode of Array product self except
2023-09-11 14:20:27 时间
Product of Array Except Self
Given an array of n integers where n > 1, nums
, return an array output
such that output[i]
is equal to the product of all the elements of nums
except nums[i]
.
Solve it without division and in O(n).
For example, given [1,2,3,4]
, return [24,12,8,6]
.
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
就是用减法实现除法。
注意零的处理。
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int size = nums.size(); vector<int> ret(size, 0); long long product = 1; int countZero = 0; int ind = -1; // 0-index for(int i = 0; i < size; i ++) { if(nums[i] == 0) { countZero ++; ind = i; } } //special case for 0 if(countZero == 0) {//no zero for(int i = 0; i < size; i ++) product *= nums[i]; for(int i = 0; i < size; i ++) ret[i] = mydivide(product, nums[i]); } else if(countZero == 1) {//1 zero for(int i = 0; i < size; i ++) { if(i != ind) product *= nums[i]; } ret[ind] = product; //others are 0s } else {//2 or more zeros ; //all 0s } return ret; } int mydivide(long long product, int divisor) {// guaranteed that divisor is not 0 int sign = 1; if((product < 0) ^ (divisor < 0)) sign = -1; if(product < 0) product = -product; if(divisor < 0) divisor = -divisor; //to here, product and divisor are positive int ret = 0; while(true) { int part = 1; //part quotient int num = divisor; while(product > num) { num <<= 1; part <<= 1; } if(product == num) { ret += part; return sign * ret; } else { num >>= 1; part >>= 1; ret += part; product -= num; } } } };
相关文章
- Leetcode: Number of Segments in a String
- Leetcode: Number of Islands II && Summary of Union Find
- Leetcode: Longest Increasing Subsequence
- Leetcode: Maximal Square
- LeetCode-1.两数之和
- LeetCode 1-5题 详解 Java版 (三万字 图文详解 LeetCode 算法题1-5 =====>>> <建议收藏>)
- [LeetCode] Power of Two
- [LeetCode] Letter Combinations of a Phone Number
- [LeetCode] Candy
- leetcode竞赛记录-第63场周赛
- 【LeetCode】58. Length of Last Word
- 【LeetCode】104. Maximum Depth of Binary Tree (2 solutions)
- LeetCode:3Sum Closest
- Leetcode Majority Element
- [LeetCode] 1296. Divide Array in Sets of K Consecutive Numbers 划分数组为连续数字的集合
- [LeetCode] 1248. Count Number of Nice Subarrays 统计优美子数组
- [LeetCode] 1005. Maximize Sum Of Array After K Negations K次取反后最大化的数组和
- [LeetCode] 818. Race Car 赛车
- [LeetCode] Maximum Length of Pair Chain 链对的最大长度
- [LeetCode] Find the Derangement of An Array 找数组的错排
- [LeetCode] Out of Boundary Paths 出界的路径
- [LeetCode] Longest Line of Consecutive One in Matrix 矩阵中最长的连续1
- [LeetCode] 421. Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字
- [LeetCode] Number of Connected Components in an Undirected Graph 无向图中的连通区域的个数
- [LeetCode] 238. Product of Array Except Self 除本身之外的数组之积
- [LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合
- [LeetCode] Compare Version Numbers 版本比较
- [LeetCode] 153. Find Minimum in Rotated Sorted Array 寻找旋转有序数组的最小值
- leetcode 191. Number of 1 Bits 位1的个数(简单)
- leetcode 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最近公共祖先(简单)
- leetcode算法235.二叉搜索树的最近公共祖先