How to find unique values in a vector c-CodePudding

I am trying to solve a coding problem where I am to check and see if a vector has unique values and if it does then return true else false.

So Far I thought of using a nested loops where you would compare the first to the last, but I am wanted to know if C has anything else then doing a o(n^2) type iteration. I saw that c has a unique function, but that would delete the unique value.

Example 1:

Input: nums = [1,2,3,1] Output: true Example 2:

Input: nums = [1,2,3,4] Output: false

CodePudding user response：

you need to create "set" structure, it makes it possible to insert values from vector and does not insert the duplicates, so you can check if the size of the set and the vector match or not.

set<int> st;
for (auto i : nums)
    st.insert(i);
return st.size() == nums.size();

CodePudding user response：

std::unique checks for consecutive duplicates and moves them to the end of the range. It does not remove them from the vector. Anyhow you can make a copy. It also returns an iterator to the end of the range of unique values (that are now in the front of the vector):

#include <iostream>
#include <vector>
#include <algorithm>

bool only_unique(std::vector<int> v) {
    std::sort(v.begin(),v.end());
    return std::unique(v.begin(),v.end()) == v.end();
}

int main(){
    std::cout << only_unique({1,2,3,1});  
    std::cout << only_unique({1,2,3,4});      
}

If you don't want to use the additional memory you can change the argument to a reference. Currently, only_unique leaves the parameter unmodified. Even if the vector is passed by reference the duplicates will still be present (just at a different position). This has O(n log n) complexity.