104 - 414第三大的数

题目

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.

示例 2:

输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:

输入: [2, 2, 3, 1]

输出: 1

解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。 存在两个值为2的数，它们都排第二。

解答

第一反应是，用set和排序，然后输出第三大的数。。

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function (nums) {
  const data = new Set(nums.sort((a, b) => b - a))
  const array = Array.from(data)
  if (array.length < 3) {
    return Math.max(...array)
  }
  return array[2]
};

Runtime: 76 ms, faster than 27.54% of JavaScript online submissions for Third Maximum Number.

Memory Usage: 38.1 MB, less than 25.00% of JavaScript online submissions for Third Maximum Number.

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        data = list(set(nums))
        data.sort(reverse=True)
        if len(data) < 3:
            return max(data)
        else:
            return data[2]

Runtime: 60 ms, faster than 84.99% of Python3 online submissions for Third Maximum Number.

Memory Usage: 15.1 MB, less than 7.69% of Python3 online submissions for Third Maximum Number.

当然go就没这么方便的函数了，得自己写。。

func thirdMax(nums []int) int {
    set := make(map[int]bool)
    for _, value := range nums {
        if _, ok := set[value]; !ok {
            set[value] = true
        }
    }
    array := make([]int, 0, len(set))
    for key := range set {
        array = append(array, key)
    }
    sort.Slice(array, func(i, j int) bool {
        return array[i] > array[j]
    })
    if len(array) < 3 {
        return array[0]
    } else {
        return array[2]
    }
}

Runtime: 8 ms, faster than 6.48% of Go online submissions for Third Maximum Number.

Memory Usage: 4 MB, less than 100.00% of Go online submissions for Third Maximum Number.

维护三个变量

作者：happy_yuxuan

链接：https://leetcode-cn.com/problems/third-maximum-number/solution/414-kong-jian-o1-shi-jian-onliang-chong-fang-fa-he/

红黑树有点厉害了。。js好像没有要手写一个。。

var thirdMax = function (nums) {
  let one = nums[0];
  let two, three
  for (const item of nums) {
    if (item === one || item === two || item === three) {
      continue
    }
    if (item > one) {
      three = two
      two = one
      one = item
    } else if (item > two || !two) {
      three = two
      two = item
    } else if (item > three || !three) {
      three = item
    }
  }
  if (three === undefined) {
    return one
  } else {
    return three
  }
};

Runtime: 60 ms, faster than 70.66% of JavaScript online submissions for Third Maximum Number.

Memory Usage: 35.1 MB, less than 100.00% of JavaScript online submissions for Third Maximum Number.

var thirdMax = function (nums) {
  let data = [nums[0]]
  for (const item of nums) {
    if (item === data[0] || item === data[1] || item === data[2]) {
      continue
    }
    if (item > data[0]) {
      data = [item, data[0], data[1]]
    } else if (item > data[1] || !data[1]) {
      data = [data[0], item, data[1]]
    } else if (item > data[2] || !data[2]) {
      data[2] = item
    }
  }
  if (data[2] === undefined) {
    return data[0]
  } else {
    return data[2]
  }
};

Runtime: 68 ms, faster than 45.74% of JavaScript online submissions for Third Maximum Number.

Memory Usage: 36.1 MB, less than 75.00% of JavaScript online submissions for Third Maximum Number.

变成数组的写法，似乎更加低效了。。

func thirdMax(nums []int) int {
    data := make([]int, 3)
    data[0] = nums[0]
    INT_MIN := ^int(^uint(0) >> 1)
    data[1], data[2] = INT_MIN, INT_MIN
    for _, value := range nums {
        if value == data[0] || value == data[1] || value == data[2] {
            continue
        }
        if value > data[0] {
            data = []int{value, data[0], data[1]}
        } else if value > data[1] {
            data = []int{data[0], value, data[1]}
        } else if value > data[2] {
            data[2] = value
        }
    }
    if data[2] == INT_MIN {
        return data[0]
    } else {
        return data[2]
    }
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Third Maximum Number.

Memory Usage: 3.2 MB, less than 100.00% of Go online submissions for Third Maximum Number.

func thirdMax(nums []int) int {
    one := nums[0]
    INT_MIN := ^int(^uint(0) >> 1)
    two, three := INT_MIN, INT_MIN
    for _, value := range nums {
        if value == one || value == two || value == three {
            continue
        }
        if value > one {
            three = two
            two = one
            one = value
        } else if value > two {
            three = two
            two = value
        } else if value > three {
            three = value
        }
    }
    if three == INT_MIN {
        return one
    } else {
        return three
    }
}

Runtime: 4 ms, faster than 91.67% of Go online submissions for Third Maximum Number.

Memory Usage: 3 MB, less than 100.00% of Go online submissions for Third Maximum Number.

go的非数组写法反而要慢一点😂

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        one = nums[0]
        two = three = -sys.maxsize - 1
        for v in nums:
            if v == one or v == two or v == three:
                continue
            if v > one:
                three = two
                two = one
                one = v
            elif v > two:
                three = two
                two = v
            elif v > three:
                three = v
        if three == -sys.maxsize - 1:
            return one
        else:
            return three

Runtime: 60 ms, faster than 84.99% of Python3 online submissions for Third Maximum Number.

Memory Usage: 14.6 MB, less than 7.69% of Python3 online submissions for Third Maximum Number.

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        INT_MIN = -sys.maxsize - 1
        data = [nums[0], INT_MIN, INT_MIN]
        for v in nums:
            if v == data[0] or v == data[1] or v == data[2]:
                continue
            if v > data[0]:
                data = [v, data[0], data[1]]
            elif v > data[1]:
                data = [data[0], v, data[1]]
            elif v > data[2]:
                data[2] = v
        if data[2] == INT_MIN:
            return data[0]
        else:
            return data[2]

Runtime: 64 ms, faster than 60.85% of Python3 online submissions for Third Maximum Number. Memory Usage: 14.4 MB, less than 7.69% of Python3 online submissions for Third Maximum Number.