在数组中查找重复项

Question

给定一个由n个整数元素组成的数组，您将如何在O（n）时间内查找该数组中是否存在重复项，而不使用任何额外的空间。如果有额外的空间，则意味着O（n）级的额外空间。Xor运算符是否以任何方式提供帮助。

Answer 1

就地基数排序后进行线性扫描

就地基数排序算法

根据您实际认为的Radix排序的时间复杂度，此解决方案为O（N）时间，尽管我个人并不这么认为。我认为，如果您不对整数排序进行线性时间假设，那么该问题将无法解决。

由于排序是就地的，因此只需要O（1）额外的存储。

代码全为C ++ 11

步骤1：基数排序

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;

}

Answer 2

这是O（n）时间使用情况和O（1）空间使用情况的解决方案！

Traverse the array. Do following for every index i of A[].

{

    check for sign of A[abs(A[i])] ;

    if positive then        make it negative by   A[abs(A[i])]=-A[abs(A[i])];

    else  // i.e., A[abs(A[i])] is negative

    this   element (ith element of list) is a repetition

}