第一题 Product of Array Except Self
第二题 XCODE 秋季班第一课 讲过的，mock到的题目
Given a sorted int array which might have repeated numbers and X, return the count of X in the array
- sorted array [1, 2, 2, 2, 4, 5, 9],
- x = 2 return 3
- x = 9 return 1
- x = 10 return 0
2 个赞
都是高频题
也考到这题，需要考虑0，因为division operation非常expensive.
public int checkForZeros(int[] arr) {
int total = 0;
for (int i : arr) {
if (i == 0) {
total = total + 1;
}
}
return total;
}
public int[] productArray(int[] arr) {
if (arr.length == 1) return new int[0];
int total = 1;
int zeroCount = checkForZeros(arr);
if (zeroCount > 1) {
for (int i = 0; i < arr.length; i++) {
arr[i] = 0;
}
} else if (zeroCount == 1) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
total = total * arr[i]; //2
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
arr[i] = total; //8
} else {
arr[i] = 0;
}
}
} else {
for (int i = 0; i < arr.length; i++)
total = total * arr[i]; // 24
for (int i = 0; i < arr.length; i++)
arr[i] = total / arr[i];
}
return arr;
}
public int[] findProduct(int[] nums) {
if(nums == null || nums.length == 0) return new int[];
int[] ans = new int[nums.length];
int product = 1;
int index = -1;
int numOfZeros = 0;
for(int i=0; i<nums.length; i++) {
if(numOfZeros > 1) return ans;
if(nums[i] == 0) {
numOfZeros++;
index = i;
continue;
}
product *= nums[i];
}
if(numOfZeros == 1) {
ans[index] = product;
return ans;
}
for(int i=0; i<nums.length; i++) {
ans[i] = product / nums[i];
}
return ans;
}
并不需要用除法啊