在数组中查找重复项
给定一个由n个整数元素组成的数组，您将如何在O（n）时间内查找该数组中是否存在重复项，而不使用任何额外的空间。
如果有额外的空间，则意味着O（n）级的额外空间。
Xor运算符是否以任何方式提供帮助。
慕码人8056858浏览 893回答 3
3回答
-
繁华开满天机
就地基数排序后进行线性扫描就地基数排序算法根据您实际认为的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 10template <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;} -
暮色呼如
这是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}
随时随地看视频慕课网APP
算法