296 · array de duplication

describe

Given a length of NNN Array of integers for arrarrarr, Returns the array after removing duplicate elements （ The relative order of array elements remains unchanged before and after removing duplicate elements ）

Wechat plus jiuzhang15 Send verification information 【 video 】 Lead the test center of real questions 、 Interview tips and other free video lessons

1≤N≤1051 \leq N \leq 10^51≤N≤105
−109≤arr[i]≤109-10^9 \leq arr[i] \leq 10^9−109≤arr[i]≤109

Examples

Input :[3,4,3,6]
Output :[3,4,6]
explain : Elements 3 repeat , So just keep one element 3
And the relative order of array elements before and after de duplication remains the same , So the element 4 Still element 3 Back , Elements 6 Still element 3,4 Back

struct  Data
{
    vector<int>vec;
};

vector<int> getUniqueArray(vector<int> &arr) {
    // write your code here
    int cur = 0;
    vector<int> ret;
    int size = arr.size();
    vector<bool> visited(size, false);

    vector<Data>dataVec(size);

    for (int i = 0; i < size; i++)
    {
        int key = arr[i] % size;
        if (key < 0)
        {
            key = key *-1;
        }
        if (dataVec[key].vec.size() == 0)
        {
            ret.push_back(arr[i]);
            dataVec[key].vec.push_back(arr[i]);
        }
        else
        {
            vector<int> tmpVec = dataVec[key].vec;
            bool bFind = false;
            for (int k = 0; k < tmpVec.size(); k++)
            {
                if (tmpVec[k] == arr[i])
                {
                    bFind = true;
                    break;
                }
            }
            if (false == bFind)
            {
                ret.push_back(arr[i]);
                dataVec[key].vec.push_back(arr[i]);
            }
        }
    }

    return ret;

}