[leetcode]Set Mismatch

임택·2021년 3월 2일
0

알고리즘

목록 보기
45/63

problem

code

possible cases

// cases after sorted in ascending order
[2, 3, 3, 4, 5, 6] => [3, 1]
[1, 2, 3, 3, 5, 6] => [3, 4]
[1, 2, 4, 4, 5, 6] => [4, 3]
[1, 2, 2, 3, 4, 5] => [2, 6]

1st try: with Map

It must be better to use duplicate, missing variables other than new int[2] cuz they are more clear to read the code.

class Solution {
    public int[] findErrorNums(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        int[] ans = new int[2]; // [duplicate, missing];
        
        for (int n: nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        
        for (int i = 1; i <= nums.length; i++) {
            if (map.containsKey(i)) {
                if (map.get(i) == 2)
                    ans[0] = i;
            } else {
                ans[1] = i;
            }
        }
        return ans;
    }
}

Time: O(N); two for loop iterating N
Space: O(N); HashMap contains N elements at most

2nd try: sorting

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    nums.sort((a, b) => a - b);
    // console.log(nums);
    
    let duplicate = -1;
    let missing = 1; // for the case when nums[0] != 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            duplicate = nums[i];
        } else if (nums[i] > nums[i - 1] + 1) {
            //when nums[0] != 1 => never
            missing = nums[i - 1] + 1;
        }
    }
    
    return [duplicate, nums[nums.length - 1] == nums.length ? missing : nums.length];
}

Time: O(nlogn); sorting
Space: O(1)

3rd try: brute force

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] ans = new int[2]; // [duplicate, missing];
        
        for (int i = 1; i <= nums.length; i++) { // 
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (i == nums[j])
                    count++;
            }
            
            if (count == 2)
                ans[0] = i;
            else if (count == 0)
                ans[1] = i;
          	
            if (nums[0] != 0 && nums[1] != 0)
                break;
          
        }
        
        return ans;
    }
}

Time: O(N^2)

profile
캬-!

0개의 댓글