LeetCode : 0217. Contains Duplicate (array)

tags:leetcode

Vscode be run code

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <unordered_map>
using std::vector;
//using std::unordered_map;
using std::unordered_set;
using namespace std;

class BaseVectorPrint {
    public:
        void BasePrint00(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << "[" <<num.at(i) << "]" << "; ";
            }
            cout << endl;
        }

        void BasePrint01(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << num[i] << "; ";
            }
            cout << endl;
        }

        void BasePrint02(vector<int>& num) {
            for (const auto &item : num) {
                cout << item << "; ";
            }
            cout << endl;
        }
        
        void TwoDimensionalPrint(vector<vector<int>> &num){
            for (int i = 0; i < num.size(); i++)
            {
                for (int j = 0; j < num[i].size(); j++)
                {
                    cout << "[" << num[i][j] << "]";
                }
                cout << endl;
            }
        }
};

class BaseSolution {
public:
    bool containsDuplicate(vector<int>& nums) {
        for (int i = 0 ; i<nums.size()-1;i++){
            //time complexity = N
            for(int j = i+1 ; j <nums.size();j++){
                //time complexity = N
                if (nums[i] == nums[j]){
                    return true;
                }
            }
        }
        return false;
    }

    //time complexity O(N^2) (N*N)
    //space complexity O(1)
};

class Solution01 {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::sort(nums.begin(),nums.end());
        // sort = LogN
        for (int i =0 ; i<nums.size()-1;i++){
        // for loop = N
            if (nums[i] == nums[i+1]){
                return true;
            }
        }
        return false;
    }

    //time complexity O(NLogN) (N * LogN)
    //space complexity O(1)
};

class Solution02 {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> RedBlackTreehashtable;
        //space black and red tree is O(N)
        for (int i = 0 ; i<nums.size();i++){
        //time for loop is O(N)
            if(!RedBlackTreehashtable.insert(nums[i]).second){
                //insert().first = key
                //insert().second = value
                return true;
            }
        }
        return false;
    }
    //time complexity O(N) 
    //space complexity O(N)
};

class Solution03 {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::map<int, int> hmap;
        
        for (int i = 0; i < nums.size(); i++) {
            if (++hmap[nums[i]] > 1) 
                return true;
        }
        
        return false;
    }
    //time complexity O(N) 
    //space complexity O(N)
};

class Solution04 {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::map<int, int> hmap;
        
        for (int i = 0; i < nums.size(); i++) {
            if (++hmap[nums[i]] > 1) 
            //input value if exist , return > 1 else return 0;
                return true;
        }
        
        return false;
    }
    //time complexity O(N) 
    //space complexity O(N)
};

int main(void)
{
    BaseVectorPrint printVector;
    Solution02 RedBlackTree;

    vector<int> test01 = {1,2,3,1};
    vector<int> test02 = {1,2,3,4};
    vector<int> test03 = {1,1,1,3,3,4,3,2,4,2};
    //vector<int> ans ;
    bool TrueOrFlase ;

    TrueOrFlase = RedBlackTree.containsDuplicate(test03);
    //printf("ans : %s\n",TrueOrFlase);
    cout << "ans (1 = True , 2 = False) : " << TrueOrFlase << endl;
    //printVector.BasePrint00(ans);

    //printf("%d\n",input_Nums);
    printf("test\n");
    system("pause");
}

tips use space transformation time complexity
hashmap , hashtable , BlackRedTree