TA貢獻1816條經驗 獲得超4個贊
就地基數排序后進行線性掃描
就地基數排序算法
根據您實際認為的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;
}
TA貢獻1853條經驗 獲得超9個贊
這是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
}
舉報