217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

217. Содержит дубли

Имеется массив целых чисел. Определите, содержит ли он дубли. Функция должна вернуть true, если некоторое число встречается в массиве более одного раза. Вернуть false, если все элементы массива различны.

// C++

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

}

};

// Java

public class Solution {

public boolean containsDuplicate(int[] nums) {

}

}

РЕШЕНИЕ

структуры данных – множество

Анализ алгоритма

Заносим элементы массива во множество set. Если очередной элемент уже присутствует во множестве, то массив содержит дубли. Оценка сложности O(nlog₂n).

При реализации на языке Java следует вместо TreeSet воспользоваться структурой HashSet, которая работает быстрее. Упорядоченность элементов во множестве в этой задаче не имеет значения.

Реализация алгоритма

class Solution

{

public:

bool containsDuplicate(vector<int>& nums)

{

set<int> s;

for(int i = 0; i < nums.size(); i++)

{

if (s.find(nums[i]) != s.end()) return true;

s.insert(nums[i]);

}

return false;

}

};

Java реализация

public class Solution

{

public boolean containsDuplicate(int[] nums)

{

// TreeSet gives TLE

HashSet<Integer> s = new HashSet<Integer>();

for(int i = 0; i < nums.length; i++)

{

if (s.contains(nums[i])) return true;

s.add(nums[i]);

}

return false;

}

}