思路
我就是用最简单的一个boolean array来记录数字出现了没，所以Space是O(n)。
Solution:
Time: O(n)
Space: O(n)
public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public ArrayList<Integer> repeatedNumber(final List<Integer> A) {
int n = A.size();
ArrayList<Integer> result = new ArrayList<>();
boolean[] arr = new boolean[n + 1];
for (int i = 0; i < n; i ++) {
int val = A.get(i);
if (arr[val]) {
result.add(val);
} else {
arr[val] = true;
}
}
for (int i = 1; i <= n; i ++) {
if (!arr[i]) {
result.add(i);
break;
}
}
return result;
}
}
官方思路
Sum(Actual) = Sum(1...N) + A - B
Sum(Actual) - Sum(1...N) = A - B.
Sum(Actual Squares) = Sum(1^2 ... N^2) + A^2 - B^2
Sum(Actual Squares) - Sum(1^2 ... N^2) = (A - B)(A + B) We can use the above 2 equations to get the value of A and B.
A + B = Sum(Actual Squares) - Sum(1^2 ... N^2) / Sum(Actual) - Sum(1...N)
A - B = Sum(Actual) - Sum(1...N)
2A = A + B + A - B
A = (A + B + A - B) / 2
B = A + B - A
Solution:
Time: O(n)
Space: O(1)
public class Solution {
// DO NOT MODIFY THE LIST
public ArrayList<Integer> repeatedNumber(final List<Integer> a) {
int arraySize = a.size();
long sumOfNumbers = getSumOfNumbers(arraySize);
long sumOfSquares = getSumOfSquares(arraySize);
long differenceNumber = getDifferenceofNumbers(a,sumOfNumbers);
long differenceSquare = getDifferenceofSquares(a,sumOfSquares);
long sumNumber = differenceSquare/differenceNumber;
int repeatedNumber = (int)((sumNumber+differenceNumber)/2);
int missingNumber = (int)(sumNumber-repeatedNumber);
ArrayList<Integer> result = new ArrayList<>();
result.add(repeatedNumber);
result.add(missingNumber);
return result;
}
private long getDifferenceofNumbers(List<Integer> a,long sumOfNumbers){
long sum = sumOfNumbers*-1;
for(Integer number:a){
long num = (long)number;
sum+=num;;
}
return sum;
}
private long getDifferenceofSquares(List<Integer> a, long sumOfSquares){
long sumSquares = sumOfSquares*-1;
for(Integer number:a){
long num = (long)number;
sumSquares+=(num*num);
}
return sumSquares;
}
private long getSumOfNumbers(double n){
return (long)(n*(n-1)/2+n);
}
private long getSumOfSquares(double n){
return (long)(n*(n+1)*(2*n+1)/6);
}
}