Java: Use length 3 Array to store Max 3 numbers


  • 0
    F

    I didn't see a similar solution so I post mine here. Basically I use a length 3 array to store max 3 numbers, and keeping adding to this array if new coming number fulfill therequirement. Return either 3rd element in array or 1st element (<3 elements).

    I feel like this is O(n+k) ? Please correct me about Big O, I am not sure about it.

    public class Solution {
        public int thirdMax(int[] nums) {
            Integer[] maxThree = new Integer[3];
            int currTotal = 0;
            for(int i=0; i<nums.length; i++){
               int newNum = nums[i];
              // Add to array
               if(!Arrays.asList(maxThree).contains(newNum) 
               &&( currTotal<maxThree.length || newNum > maxThree[currTotal-1])){
                   if(currTotal < maxThree.length){
                       currTotal ++;
                   }
                   int j = currTotal-1;
                   while(j>0 && maxThree[j-1] < newNum){
                       maxThree[j]=maxThree[j-1];
                       j--;
                   }
                   maxThree[j]=newNum;
               }
            }
            if(currTotal < maxThree.length){ //3rd max not existed
                return maxThree[0];
            }
            return maxThree[currTotal-1];
        } 
    }
    

  • 0
    K

    Besides min-heap and max-heap method, we can use quicksort for kth max.

    class Solution(object):
        def thirdMax(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            def quicksort(nums, k):
                # get kth max num in nums
                if len(nums) == k:
                    return min(nums)
                pivot, less, greater = random.choice(nums), [], []
                for x in nums:
                    if x > pivot:
                        greater.append(x)
                    elif x < pivot:
                        less.append(x)
                if len(greater) + 1 >= k:
                    return quicksort([pivot] + greater, k)
                else:
                    return quicksort(less + [pivot], k - len(greater))
                
            nums = set(nums)
            if len(nums) < 3:
                return max(nums)
            return quicksort(nums=list(nums), k=3)
    

    This one is fast, 33ms in Python.

    class Solution(object):
        def thirdMax(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            max1, max2, max3 = -sys.maxint, -sys.maxint, -sys.maxint
            for x in nums:
                if x > max1:
                    max1, max2, max3 = x, max1, max2
                elif max1 > x > max2:
                    max2, max3 = x, max2
                elif max2 > x > max3:
                    max3 = x
            return max3 if max3 != -sys.maxint else max1
    

Log in to reply
 

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