296 · 数组去重

描述

给定一个长度为NNN的整数数组arrarrarr，返回去掉重复元素之后的数组（去掉重复元素前后数组元素相对次序不变）

微信加 jiuzhang15 发送验证信息【视频】领真题考点、面试技巧等免费视频课

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

样例

输入:[3,4,3,6]
输出:[3,4,6]
解释:元素3重复，所以只需要保留一个元素3
而且去重前后数组元素相对次序不变，所以元素4还在元素3后面，元素6还在元素3，4后面

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;

}