Make writing a habit together! This is the 12th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I. Problem description

Give you an integer array nums. Returns true if any value appears in the array at least twice; Return false if each element in the array is different.

Title link: Duplicate elements exist

Two, the title requirements

Sample 1

Nums = [1,2,3,1] output: trueCopy the code

The sample 2

Input: nums = [1,2,3,4] output: falseCopy the code

inspection

1. Hash table, sorting, and weight judgment 2. The recommended time is 10 to 25 minutesCopy the code

Third, problem analysis

This is a simple question, mainly to judge the idea of repeating elements. Don’t start with a double for loop, it will time out.

The following alternatives are available: the guys you understand ￣ 3￣) the guys you understand

1. Hash count

The hash table is used to store the number of occurrences of each number. If the number is found to have occurred during storage, return true, otherwise return false.

2. The set of storage

A feature of set is that the saved duplicate elements are automatically skipped and not stored.

Therefore, an array with repeating elements must be smaller after going through a set.

3. Rank judgment

How does sorting determine duplicate elements?

First, taking example 1 as an example, the sorted result is:

1 1 2 3
Copy the code

Start with the second number and return true if it is the same as the previous number, otherwise return true;

Four, coding implementation

1. Hash count

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int i,n=nums.size(a);/ / initialization
        map<int.int>m;// hash count
        for(i=0; i<n; i++) { m[nums[i]]++;/ / count
            if(m[nums[i]]>=2)// Conditional judgment
                return true;
        }
        return false; }};Copy the code

2. The set of storage

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int i,n=nums.size(a);/ / initialization
        set<int>s;/ / set storage
        for(i=0; i<n; i++) s.insert(nums[i]);/ / insert
        if(s.size()<n)// Find that the array length is smaller and there are duplicate elements
            return true;
        else    
            return false; }};Copy the code

3. Rank judgment

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int i,n=nums.size(a);/ / initialization
        sort(nums.begin(),nums.end());/ / sorting
        for(i=1; i<n; i++)if(nums[i]==nums[i- 1])/ / to heavy
                return true;
        return false; }};Copy the code

V. Test results

On the whole, all three methods are about the same. If I had to compare them, the third one is better.