题解 | #数组中重复的数字#

数组中重复的数字

https://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524

解题思路

这个题很简单,利用了哈希表的性质,判断当前的元素是否在哈希表内,如果在的话,就说明该数是重复的元素,就返回该数。

复杂度

  • 时间复杂度:O(n);
  • 空间复杂度:O(n)。

代码

C++

// 写法一
#include <unordered_map>
class Solution {
public:
    int duplicate(vector<int>& numbers) {
        unordered_map<int, int> mp;
	  
        for(int i = 0; i<numbers.size(); i++)
        {
            if(mp.find(numbers[i]) == mp.end())
            {
                mp[numbers[i]]++;
            }
            else {
                return numbers[i];
            }
        }
        return -1;
    }
};


// 写法二
class Solution {
public:
    int duplicate(vector<int>& numbers) {
        map<int, int> mp;

        for(int i = 0; i < numbers.size(); i++)
        {
            if(++mp[numbers[i]] > 1)
            {
                return numbers[i];
            }
        }
        return -1;
    }
};

Python

class Solution:
    def duplicate(self , numbers: List[int]) -> int:
        hashList = {}

        for i in numbers:
            if i in hashList:
                return i
            else:
                hashList[i] = 1    
				
        return -1
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务