題目描述

給你一個整數(shù)數(shù)組 nums，返回 數(shù)組 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積 。

題目數(shù)據(jù) 保證 數(shù)組 nums之中任意元素的全部前綴元素和后綴的乘積都在 32 位 整數(shù)范圍內(nèi)。

請 不要使用除法，且在 O(n) 時間復(fù)雜度內(nèi)完成此題。

示例 1:

輸入: nums = [1,2,3,4]
輸出: [24,12,8,6]
示例 2:

輸入: nums = [-1,1,0,-3,3]
輸出: [0,0,9,0,0]

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保證 數(shù)組 nums之中任意元素的全部前綴元素和后綴的乘積都在 32 位 整數(shù)范圍內(nèi)

進(jìn)階：你可以在 O(1) 的額外空間復(fù)雜度內(nèi)完成這個題目嗎？（ 出于對空間復(fù)雜度分析的目的，輸出數(shù)組 不被視為 額外空間。）

代碼

class Solution {public int firstMissingPositive(int[] nums) {Set<Integer> set = new HashSet<>();//把nums[i]依次都放入集合當(dāng)中，用來記錄是否存在for (int i = 0; i < nums.length; i++) {if (nums[i]>0){set.add(nums[i]);}}//從1開始遍歷，如果缺少了當(dāng)前i這個正數(shù)就直接返回for (int i = 1; i <= nums.length+1; i++) {if (!set.contains(i)){return i;}}return 0;}
}