题目:一个大小为N的数组,里面是N个整数,怎样去除重复,
要求时间复杂度为O(n),空间复杂度为O(1).
//下面的思路没问题,但算法有问题,修正后的算法见后面.
/// <summary>
/// 需要除掉重复的整数的数组,注意这里我没有处理负数情况,
/// 其实负数情况只要先用0快排分一下组,然后各自用以下算法进行处理即可。
/// 另外因为是整数,这里没考虑32位符号位,只考虑31位。
/// 题目分析:从要求来看,如果一个数组是排好序的,除掉重复就很简单,因此就转换成了
/// 排序算法寻找,这种算法需要满足:线性时间,常量内存,原地置换。但纵观这么多算法,比较排序肯定不行,
/// 那么就只有基数排序,桶排序和计数排序,但基数排序依赖于位排序,而且要求位排序是稳定的,
/// 且不能过多使用辅助空间,计数排序排除,因为计数排序无法原地置换,桶排序也需要辅助空间,所以最后考虑用
/// 基数排序。但问题是如何选择位排序,因为位上只有0和1,因此有其特殊性,使用快排的分组就可以达到线性,
/// 但问题是这种算法虽然是线性,原地置换,但不稳定。所以要利用一种机制来确保快排是稳定的。经过一段时间思考,
/// 发现,如果从高位开始排序,假设前K位是排好的,对K+1进行排序时,只针对前K位的相同的进行,前K位不相同,也不可
/// 能相等,第K+1位也不影响结果,而前K位相同的排序,就不怕快排的不稳定了,因为这个不稳定不会影响到最终结果。
/// 下面就是算法:
/// </summary>
/// <param name="A"></param>
private void BitSortAndDelRepeatorsA(int[] A)
{
//获取数组长度
int theN = A.Length;
//从高位到低位开始排序,这里从31位开始,32位是符号位不考虑,或者单独考虑。
for (int i = 31; i >= 1; i--)
{
//当前排序之前的值,只有该值相同才进行快排分组,如果不相同,则重新开始另外一次快排
//这很关键,否则快排的不稳定就会影响最后结果.
int thePrvCB = A[0] >> (i) ;
//快排开始位置,会变化
int theS = 0;
//快排插入点
int theI = theS;
//整数基元,就选择快排开始位置的数.
int theAxNum = A[theI];
//2进制基数,用于测试某一位是否为0
int theBase = 1 << (i-1);
//位基元,
int theAxBit = (theAxNum >> (i-1)) & 1;//(A[theI] & (theBase)) > 0 ? 1 : 0;
//分段快排,但总体上时间复杂度与快排分组一样.
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;
}
//如果相同,则按快排处理
int theAJ = (A[j] >> (i - 1)) & 1;//(A[j] & (theBase)) > 0 ? 1 : 0;
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();
}
===================================================
排序算法修正部分
/// <summary>
/// 需要除掉重复的整数的数组,注意这里我没有处理负数情况,
/// 其实负数情况只要先用0快排分一下组,然后各自用以下算法进行处理即可。
/// 另外因为是整数,这里没考虑32位符号位,只考虑31位。
/// 题目分析:从要求来看,如果一个数组是排好序的,除掉重复就很简单,因此就转换成了
/// 排序算法寻找,这种算法需要满足:线性时间,常量内存,原地置换。但纵观这么多算法,比较排序肯定不行,
/// 那么就只有基数排序,桶排序和计数排序,但基数排序依赖于位排序,而且要求位排序是稳定的,
/// 且不能过多使用辅助空间,计数排序排除,因为计数排序无法原地置换,桶排序也需要辅助空间,所以最后考虑用
/// 基数排序。但问题是如何选择位排序,因为位上只有0和1,因此有其特殊性,使用快排的分组就可以达到线性,
/// 但问题是这种算法虽然是线性,原地置换,但不稳定。所以要利用一种机制来确保快排是稳定的。经过一段时间思考,
/// 发现,如果从高位开始排序,假设前K位是排好的,对K+1进行排序时,只针对前K位的相同的进行,前K位不相同,也不可
/// 能相等,第K+1位也不影响结果,而前K位相同的排序,就不怕快排的不稳定了,因为这个不稳定不会影响到最终结果。
/// 下面就是算法:
/// </summary>
/// <param name="A"></param>
private void BitSortAndDelRepeatorsA(int[] A)
{
//获取数组长度
int theN = A.Length;
//从高位到低位开始排序,这里从31位开始,32位是符号位不考虑,或者单独考虑。
for (int i = 31; i >= 1; i--)
{
//当前排序之前的值,只有该值相同才进行快排分组,如果不相同,则重新开始另外一次快排
//这很关键,否则快排的不稳定就会影响最后结果.
int thePrvCB = A[0] >> (i) ;
//快排开始位置,会变化
int theS = 0;
//快排插入点
int theI = theS-1;
//2进制基数,用于测试某一位是否为0
int theBase = 1 << (i-1);
//位基元始终为0,
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;
j--;//重新开始排,回朔一位.
continue;
}
//如果前面的数相同,则寻找第1个1,thI指向其
//如果相同,则按快排处理
int theAJ = (A[j] & (theBase)) > 0 ? 1 : 0; ;//(A[j] & (theBase)) > 0 ? 1 : 0;(A[j] >> (i - 1)) & 1
//如果是重新开始排,则寻找第1个1,并人theI指向其.这可以减少交换,加快速度.
if (theI < theS)
{
if (theAJ == 0)
{
continue;
}
theI = j;//Continue保证J从theI+1开始.
continue;
}
//交换.
if (theAJ <= theAxBit)
{
int theTmp = A[j];
A[j] = A[theI];
A[theI] = theTmp;
theI++;
}
}
}
}
经过测试,算法复杂度<32*n。
后记:其实这个面试题的实用价值还是非常大的,这里是整数,如果是字符串排序也可以采用类似算法,而且空间要求比较小。
声明:该算法是本人的原创算法,转载请注明出处,谢谢!
注,本算法也不是稳定的.
另外:面试题集锦,大家可以去July的博客看看,会很有收获:http://blog.csdn.net/v_JULY_v
分享到:
相关推荐
用java编的一个小程序,输入10个整数,去掉其中重复的数后输出
用算法去除数组中重复的数字(不使用查重函数)通过嵌套for循环和if条件判断实现,用算法去除数组中重复的数字(不使用查重函数)通过嵌套for循环和if条件判断实现
该算法是基于重复数据的一个简单的算法,适合各种语言,比网上的其他的算法简洁,更容易理解,算法,适合各种编程语言,如,数组,集合
找到出现最多的数字和出现的次数,去除字符串中重复的数字,对去重后的字符串排序,代码规范
先声明一个数组,这个数组中可能会存在重复的元素,而且顺序也是杂乱的,要求将这个数组中的重复元素排除掉并将新得到的数组进行递增排序
线性模糊微分方程的新算法,张璐,,本文利用模糊值函数分析学的结构元表述方法,讨论了线性模糊微分方程的求解问题,对于一类线性模糊微分方程的通解给出了基于模糊
1. (5 分) 欧几里德算法利用算术基本定理 (任何一个正整数去除另一个正整数, 3. (5 分) 求解递归方程,假设 n ≤ 3 时 T(n)为常数,T
1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序3】 题目:打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和...
java经典算法题例。参赛必做。 【程序14】 题目:两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比,c说他不和x,z比,请编程序找...
双整数数组去重复,一千万少于两秒。加入有负数时0的处理。去除a数组和b数组相同的成员。只支持整数数组。如果文本数组里面是数字,可以转成整数数组再处理。数组可以是乱序,也可以是负数。@yjwfdc。Tags:数组去...
本代码文档利用回溯法思想,实现了n位正整数去掉k位数字得到最小数,并且含有测试代码,非常简单,详细,准确!
重复数据删除技术中的关键技术MD5算法及改进
该程序为matlab 程序,可有效去除光纤陀螺角振动噪声。
鲁棒时间序列平滑算法是一种用于去除时间序列中异常值的算法。它可以有效地去除因噪声、异常值等原因导致的序列突变,同时保留序列的趋势信息。该算法采用了一种基于加权移动平均的方法,通过对每个数据点进行加权...
提出一种去除文字图像中干扰线的通用算法.通过将图像转换为便于操作的基本图形及高级图形,去除了图像的冗余同时获得了图像的几何信息,然后将对干扰线的检测看作对图像主曲线的检测,并将检测环节作为去除干扰线的关键...
20.现在输入n个数字,以逗号,分开;然后可选择升或者降序排序;按提交键就在另一页面显示按什么排序,结果为,提供reset 五. 数据库部分 1、用两种方式根据部门号从高到低,工资从低到高列出每个员工的信息。 2...
主要介绍了Python实现连接两个无规则列表后删除重复元素并升序排序的方法,涉及Python针对列表的合并、遍历、判断、追加、排序等操作技巧,需要的朋友可以参考下
将数组中相同的数删掉,剩余的数从小到大排序
matlab中如何去掉数组中重复的值