在数组中查找重复项

Question

给定一个n个整数元素的数组,如何在不使用任何额外空间的情况下在O(n)时间内找到数组中是否存在重复项.

额外的空间意味着额外的O(n)空间.

Xor操作员是否以任何方式提供帮助.

Answer 1

如果没有其他信息,这个问题似乎是不可解决的,因为这是元素区分问题,在您所需的时间内,您提供的限制无法解决.

你可以允许:

(1)更多内存并使用哈希表/哈希集并满足O(n)时间标准.[迭代数组,检查一个元素是否在哈希表中,如果你有dupes,否则 - 将元素插入表中并继续].

(2)更多时间,对数组[O(nlogn)]进行排序并满足子线性空间标准.[排序后,遍历数组,并为每个数组a[i] , a[i+1]检查它们是否相同.如果你没有找到相同的一对,你没有欺骗]

编辑:这个声明的证据有点冗长,需要这里不支持的数学符号(旁注:我们真的需要tex支持),但我们的想法是我们将问题建模为代数计算树(这是一个公平的假设没有允许散列,并且在处置时不变空间),那么,Ben Or在他的文章" 代数计算树的下边界"(1983)(在声望的ACM中发表)中证明,元素清晰度是Omega(nlogn)该模型下的问题.Lubiw表明,同样的结论也适用于1991年将自己局限于整数:整数元素明显问题的下界,但这些文章得出结论,在代数树计算模型下 - 整数不同问题是Omega(nlogn)问题.

Answer 2

就地Radix排序后跟线性扫描

到位基数排序算法

根据你实际考虑的Radix排序的时间复杂度,这个解决方案是O(N)时间,虽然我的个人意见不是这样.我认为如果你不对整数排序做出线性时间假设,那么问题是无法解决的.

由于排序是就地的,因此只需要额外的O(1)存储空间.

代码全是C++ 11

第1步:Radix排序到位

template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin)
{
    if (zerosEnd+1 >= onesBegin-1 || mask == 0) 
        return;

    int zerosEnd2 = zerosEnd;
    int onesBegin2 = onesBegin;
    while(zerosEnd2+1 <= onesBegin2-1)
    {
        // swap ones to the right
        if ((myArray[zerosEnd2+1] & mask) != 0)
        {
            std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]);
            --onesBegin2;
        }
        else
            ++zerosEnd2;
    }

    mask >>= 1;

    //recurse on lhs
    RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1);

    //recurse on rhs
    RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin);
}

template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void InPlaceRadixSort(std::vector<T>& myArray)
{
    int zerosEnd = -1;
    int onesBegin = static_cast<int>(myArray.size());
    T mask = static_cast<T>(1) << sizeof(T)*8-1;
    while(zerosEnd+1 <= onesBegin-1)
    {
        if ( (myArray[zerosEnd+1] & mask) != 0)
        {
            std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]);
            --onesBegin;
        }
        else
            ++zerosEnd;
    }

    mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype
    //recurse on lhs
    RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1);
    //recurse on rhs
    RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size()));

    // swap negatives to the front
    auto iterSmallest = std::min_element(myArray.begin(), myArray.end());
    if (*iterSmallest < 0)
    {
        std::reverse(myArray.begin(), myArray.end());
        iterSmallest = std::min_element(myArray.begin(), myArray.end());
        std::reverse(myArray.begin(), iterSmallest+1);
        std::reverse(iterSmallest+1, myArray.end());
    }
}

第2步:线性扫描重复元素

for (size_t i=0, j=1; j<myArray.size(); ++i,++j)
{
    if (myArray[i] == myArray[j])
    {
        std::cout << "Found duplicate element " << myArray[i];
    }
}

完整代码

#include <iostream>
#include <string>
#include <vector>
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <type_traits>
using namespace std;
#define N 10

template <typename T>
void PrintArray(const std::vector<T>& myArray)
{
    for (auto&& element : myArray)
    {
        std::cout << element << std::endl;
    }
}

template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin)
{
    if (zerosEnd+1 >= onesBegin-1 || mask == 0) 
        return;

    int zerosEnd2 = zerosEnd;
    int onesBegin2 = onesBegin;
    while(zerosEnd2+1 <= onesBegin2-1)
    {
        // swap ones to the right
        if ((myArray[zerosEnd2+1] & mask) != 0)
        {
            std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]);
            --onesBegin2;
        }
        else
            ++zerosEnd2;
    }

    mask >>= 1;

    //recurse on lhs
    RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1);

    //recurse on rhs
    RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin);
}

template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void InPlaceRadixSort(std::vector<T>& myArray)
{
    int zerosEnd = -1;
    int onesBegin = static_cast<int>(myArray.size());
    T mask = static_cast<T>(1) << sizeof(T)*8-1;
    while(zerosEnd+1 <= onesBegin-1)
    {
        if ( (myArray[zerosEnd+1] & mask) != 0)
        {
            std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]);
            --onesBegin;
        }
        else
            ++zerosEnd;
    }

    mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype
    //recurse on lhs
    RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1);
    //recurse on rhs
    RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size()));

    // swap negatives to the front
    auto iterSmallest = std::min_element(myArray.begin(), myArray.end());
    if (*iterSmallest < 0)
    {
        std::reverse(myArray.begin(), myArray.end());
        iterSmallest = std::min_element(myArray.begin(), myArray.end());
        std::reverse(myArray.begin(), iterSmallest+1);
        std::reverse(iterSmallest+1, myArray.end());
    }
}

int main() {
    srand(time(NULL));
    std::vector<int> myArray(N);
    for (size_t i=0;i<myArray.size();++i)
    {
        myArray[i] = rand() % 100 * (rand() % 2 == 1?-1:1);
    }

    std::cout << "Vector before radix sort: " << std::endl;
    PrintArray(myArray);
    InPlaceRadixSort(myArray);
    std::cout << "Vector after radix sort: " << std::endl;
    PrintArray(myArray);

    for (size_t i=0, j=1; j<myArray.size(); ++i,++j)
    {
        if (myArray[i] == myArray[j])
        {
            std::cout << "Found duplicate element " << myArray[i];
        }
    }
    return 0;
}

现场演示