beats most of the solution 99% java


  • 2
    E

    Here is the algorithm:
    First sort the input.
    Then check whether element at position i , i + 1 , and i+2 are the same or not.
    If the three elements are the same , then add two to the loop counter , if they are not the same then element at position i is the missing one return it.
    What happens if the missing element is at position nums.length-1 e.g. [1,1,1,2,2,2,3,3,3,4,4,4,5] ?
    to handle this case we need to return nums[nums.length-1] at the end.

    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        if(nums.length == 0 ) return 0;
        for(int i = 0; i < nums.length-2; i++ ){
             if(nums[i] != nums[i+1] || nums[i] != nums[i+2]){
                 return nums[i];
             }else{
                 i += 2;;
             }
        }
           return nums[nums.length-1];
    }

  • 0
    J

    This is not a linear runtime solution, but, if you want to do in this way, you don't need to set a bool flag. Why don't you directly return nums[nums.length-1] in the end :)


  • 0
    E

    @johnucm what do you mean by this is not a linear runtime solution, the solution is O(n).
    What if the length is 0, nums[nums.length-1] will hit an array index out of bounds exception .


  • 0
    J

    @ebou The runtime of Arrays.sort is O(nlogn). And if you wanna consider the length = 0, we may check this at first.


  • 0
    E

    i see your point


Log in to reply
 

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