1133. 最大唯一数 🔒

题目描述

给你一个整数数组 A，请找出并返回在该数组中仅出现一次的最大整数。

如果不存在这个只出现一次的整数，则返回 -1。

示例 1：

输入：[5,7,3,9,4,9,8,3,1]
输出：8
解释： 
数组中最大的整数是 9，但它在数组中重复出现了。而第二大的整数是 8，它只出现了一次，所以答案是 8。

示例 2：

输入：[9,9,8,8]
输出：-1
解释： 
数组中不存在仅出现一次的整数。

提示：

1 <= A.length <= 2000
0 <= A[i] <= 1000

解法

方法一：计数 + 倒序遍历

注意到题目的数据范围，我们可以使用一个长度为 \(1001\) 的数组来统计每个数字出现的次数，然后倒序遍历数组，找到第一个出现次数为 \(1\) 的数字即可。如果没有找到，则返回 \(-1\)。

时间复杂度 \(O(n + M)\)，空间复杂度 \(O(M)\)。其中 \(n\) 为数组长度；而 \(M\) 为数组中出现的最大数字，本题中 \(M \leq 1000\)。

Python3JavaC++GoTypeScriptJavaScript

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        return max((x for x, v in cnt.items() if v == 1), default=-1)

class Solution {
    public int largestUniqueNumber(int[] nums) {
        int[] cnt = new int[1001];
        for (int x : nums) {
            ++cnt[x];
        }
        for (int x = 1000; x >= 0; --x) {
            if (cnt[x] == 1) {
                return x;
            }
        }
        return -1;
    }
}

class Solution {
public:
    int largestUniqueNumber(vector<int>& nums) {
        int cnt[1001]{};
        for (int& x : nums) {
            ++cnt[x];
        }
        for (int x = 1000; ~x; --x) {
            if (cnt[x] == 1) {
                return x;
            }
        }
        return -1;
    }
};

func largestUniqueNumber(nums []int) int {
    cnt := [1001]int{}
    for _, x := range nums {
        cnt[x]++
    }
    for x := 1000; x >= 0; x-- {
        if cnt[x] == 1 {
            return x
        }
    }
    return -1
}

function largestUniqueNumber(nums: number[]): number {
    const cnt = Array(1001).fill(0);
    for (const x of nums) {
        ++cnt[x];
    }
    for (let x = 1000; x >= 0; --x) {
        if (cnt[x] === 1) {
            return x;
        }
    }
    return -1;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var largestUniqueNumber = function (nums) {
    const cnt = Array(1001).fill(0);
    for (const x of nums) {
        ++cnt[x];
    }
    for (let x = 1000; x >= 0; --x) {
        if (cnt[x] === 1) {
            return x;
        }
    }
    return -1;
};

1133. 最大唯一数 🔒

题目描述

解法

方法一：计数 + 倒序遍历

评论