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;
    }
}

results matching ""

    No results matching ""