Golang the easiest way to solve in O(n)


  • 0
    D

    1. Discovering the duplicated number
    If the array is in order, then we can simply look up a duplicated value by a method of Binary Search in O(ln n), but the problem does not guarantee that the array is sorted.

    Since what we are commonly interested in is that finding the duplicated number with the best performance, my approach is that counting a number of appearances of each value by visiting elements in an array. (O(n) time complexity). After the complete iteration of the given array and marking the appearance with a key=value format in a map, we know that the element appeared twice is the value that we are looking for.

    2. Obtaining the missing number
    The problem limits the array only consists with integers 1 >= n. This implies that the original given array would perfectly have a length of n, but with a missing number. For example, [2,3,3,4,5,6] an array has a length of 6 but there is a missing number which never appeared in our map. We go through the map with a for loop and discover if the current visiting element has a value of 0.

    This is the complete code in Go.

    func findErrorNums(nums []int) []int {
    	res := make([]int, 2)
    
    	m := make(map[int]int)
    	for i := 0; i < len(nums); i++ {
    		m[nums[i]] += 1
    	}
    
    	for k, v := range m {
    		if v > 1 {
    			res[0] = k
    		}
    	}
    
    	for i := 1; i <= len(nums); i++ {
    		if m[i] == 0 {
    			res[1] = i
    			break
    		}
    	}
    
    	return res
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.