Remove Duplicate Numbers in Array
题目:
Given an array of integers, remove the duplicate numbers in it.
You should:
1. Do it in place in the array.
2. Move the unique numbers to the front of the array.
3. Return the total number of the unique numbers.
分析:
解法1用hashmap,可以做到O(n)time, O(n)space
注意到HashMap<Integer, Boolean>容易忘记首字母大写,而且要用全名
注意到hash.containsKey()方法
注意到hash.keySet()方法
解法2用sort,可以做到O(nlogn)time, O(1)space
注意到Arrays.sort(nums)不要忘记写s,不要忘记不要忘记
这种做法需要注意实际测试
1. size等于0的case要专门写
2. 最后返回值是index + 1
解法1:
public class Solution {
/**
* @param nums an array of integers
* @return the number of unique integers
*/
public int deduplication(int[] nums) {
// Write your code here
HashMap<Integer, Boolean> hash = new HashMap<Integer, Boolean>();
for (int i = 0; i < nums.length; i++) {
if (!hash.containsKey(nums[i]) ) {
hash.put(nums[i], true);
}
}
int index = 0;
for (int i : hash.keySet() ) {
nums[index] = i;
index++;
}
return index;
}
}
解法2:
public class Solution {
/**
* @param nums an array of integers
* @return the number of unique integers
*/
public int deduplication(int[] nums) {
// Write your code here
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != nums[index]) {
nums[index + 1] = nums[i];
index += 1;
}
}
return index + 1;
}
}