Skip to content

Latest commit

 

History

History
173 lines (134 loc) · 3.62 KB

File metadata and controls

173 lines (134 loc) · 3.62 KB

English Version

题目描述

给你一个 不包含 任何零的整数数组 nums ,找出自身与对应的负数都在数组中存在的最大正整数 k

返回正整数 k ,如果不存在这样的整数,返回 -1

 

示例 1:

输入:nums = [-1,2,-3,3]
输出:3
解释:3 是数组中唯一一个满足题目要求的 k 。

示例 2:

输入:nums = [-1,10,6,7,-7,1]
输出:7
解释:数组中存在 1 和 7 对应的负数,7 的值更大。

示例 3:

输入:nums = [-10,8,6,7,-2,-3]
输出:-1
解释:不存在满足题目要求的 k ,返回 -1 。

 

提示:

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • nums[i] != 0

解法

方法一:哈希表 + 枚举

我们先用哈希表 $s$ 记录数组中的所有元素,然后枚举数组中的每个元素 $x$,如果 $x$ 为正数,且 $-x$ 在哈希表 $s$ 中,更新答案。

时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为数组的长度。

Python3

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        ans = -1
        s = set(nums)
        for v in s:
            if -v in s:
                ans = max(ans, v)
        return ans

Java

class Solution {
    public int findMaxK(int[] nums) {
        int ans = -1;
        Set<Integer> s = new HashSet<>();
        for (int v : nums) {
            s.add(v);
        }
        for (int v : s) {
            if (s.contains(-v)) {
                ans = Math.max(ans, v);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int findMaxK(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int ans = -1;
        for (int& v : nums) {
            if (s.count(-v)) {
                ans = max(ans, v);
            }
        }
        return ans;
    }
};

Go

func findMaxK(nums []int) int {
	s := map[int]bool{}
	for _, v := range nums {
		s[v] = true
	}
	ans := -1
	for v := range s {
		if s[-v] && ans < v {
			ans = v
		}
	}
	return ans
}

TypeScript

function findMaxK(nums: number[]): number {
    const set = new Set(nums);
    let res = -1;
    for (const num of set) {
        if (set.has(-num)) {
            res = Math.max(num, res);
        }
    }
    return res;
}

Rust

use std::collections::HashSet;
impl Solution {
    pub fn find_max_k(nums: Vec<i32>) -> i32 {
        let set = nums.into_iter().collect::<HashSet<i32>>();
        let mut res = -1;
        for &num in set.iter() {
            if set.contains(&(-num)) {
                res = res.max(num);
            }
        }
        res
    }
}

...