Solution by Jackpon


  • 0
    J

    Approach #1 Brute Force [Wrong]

    Intuition

    The intuition tell me that should sort the nums .while the nums's length <3,return the maxnum. else return the nums[nums.length-3].

    Java

    public int thirdMax(int[] nums) {
              Arrays.sort(nums);
              int value=nums[0];
    
              if (nums.length<3) 
                for (int i = 0; i < nums.length; i++) 
                  	value=Math.max(value, nums[i]);
              else 
    			 value=nums[nums.length-3];
              return value;
        }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$


    Approach #2 Sliding Window [Accepted]

    Algorithm

    The intuition is naive. Because I don't thought about the duplicate value, just like the nums=[1,2,2,3], the function must return the 1. so I ignore the duplicate value by set the 'count=0'. when 'count==2' , it mean that we found the Third Maximum Number.

    Java

    public int thirdMax(int[] nums) {
    	Arrays.sort(nums);
    	int count=0,value=nums[0];
    	
    	if (nums.length<3) {
    		for (int i = 0; i < nums.length; i++) 
    			value=Math.max(value, nums[i]);
    	}else {
    		for (int i = nums.length-1; i > 0; i--) {
    			if (nums[i]>nums[i-1]) {
    				count++;
    				if (count==2) {
    					value=nums[i-1];
    					break;
    				} 
    			}
    		}
    		if(count<2)
    			value=nums[nums.length-1];
    	}
    	
    	return value;
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$

Log in to reply
 

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