将写内容过程中比较好的一些内容片段备份一次，下边内容内容是关于腾讯面试题（除掉N个整数中重复数）解题（线性时间，原地置换排序算法）(C#)的内容，希望能对码农们也有好处。
private void BitSortAndDelRepeatorsA(int[] A)
{
int theN = A.Length;
for (int i = 31; i >= 1; i--)
{
int thePrvCB = A[0] >> (i) ;
int theS = 0;
int theI = theS;
int theAxNum = A[theI];
int theBase = 1 << (i-1);
for (int j = 1; j < theN; j++)
{
int theTmpPrvCB = A[j] >> (i);
if (theTmpPrvCB != thePrvCB)
{
A[theS] = A[theI];
A[theI] = theAxNum;
theS = j;
theI = theS;
theAxNum = A[theI];
theAxBit = A[theI] & theBase;
thePrvCB = theTmpPrvCB;
continue;
}
if (theAJ <= theAxBit)
{
theI++;
int theTmp = A[j];
A[j] = A[theI];
A[theI] = theTmp;
}
}
A[theS] = A[theI];
A[theI] = theAxNum;
}
}
除掉重复数:只要对上述排序结果进行一次遍历处理即可.
private int[] DeleteRepeatedInt(int[] A)
{
int N = A.Length;
for (int i = 1; i <= 32; i++)
{
CountSort2(A, i);
}
int thePreNum = int.MinValue;
List<int> theRet = new List<int>();
for (int i = 0; i < N; i++)
{
if (A[i] != thePreNum)
{
theRet.Add(A[i]);
thePreNum = A[i];
}
}
return theRet.ToArray();
}
===================================================排序算法修正部分
private void BitSortAndDelRepeatorsA(int[] A)
{
int theN = A.Length;
for (int i = 31; i >= 1; i--)
{
int thePrvCB = A[0] >> (i) ;
int theS = 0;
int theI = theS-1;
int theBase = 1 << (i-1);
int theAxBit = 0;
for (int j = 0; j < theN; j++)
{
int theTmpPrvCB = A[j] >> (i);
if (theTmpPrvCB != thePrvCB)
{
theS = j;
theI = theS - 1;
theAxBit = 0;
thePrvCB = theTmpPrvCB;
continue;
}
if (theI < theS)
{
if (theAJ == 0)
{
continue;
}
continue;
}
if (theAJ <= theAxBit)
{
int theTmp = A[j];
A[j] = A[theI];
A[theI] = theTmp;
theI++;
}
}
}
}
网友评论