一个数组的元素为1~n，在o(n)的时间内对数组排序
|
点击此处返回总目录
一、长度为len的数组元素刚好为1-n，对数组进行排序。 【题目】 比如数组：[10,6,9,5,2,8,4,7,1,3] 希望得到：[1,2,3,4,5,6,7,8,9,10]
【分析】 对于一般的数组，排序要花nlogn的时间。 但是，如果一个数组，长度为n。元素刚好是1~n。对这n个数排序，可以在o(n)时间内完成。 代码如下： for(int i = 0 ;i<nums.length;i++){ while(nums[i] != i+1){ swap(nums[i], nums[nums[i]-1]); } }
比如： [10,6,9,5,2,8,4,7,1,3 ] //a[0]!=1。把10和3交换 [1, 4,3,5,2,6,7,8,9,10] //7已经归位。a[1]!=1。4和5交换。 [1, 5,3,4,2,6,7,8,9,10] //4已经归位。a[1]!=2，5和2交换。 [1, 2,3,4,5,6,7,8,9,10] //5已经归位。顺次检查到最后，都不需要交换。
当第一个位置不是10的时候，就把10和应该放10的元素交换，这样10就放到应该放的位置了。 再看看第一位置是多少，不是1，就把这个元素放到应该放的位置。直到第一个元素是1。 接下来再看看第二个位置是不是2，不是就放到应该放的位置。 ...
【代码】
【结果】
二、有重复数字的情况下，把数字排序。 【题目】 数组长度为n，元素为1-n。其中某些数字被其他的替换了。 希望没有被替换的数字放到本来的位置。 比如数组：[10,6,9,3,2,8,4,7,1,3 ] 希望得到：[1,2,3,4,3,6,7,8,9,10 ]
【分析】 比如，[10,6,9,3,2,8,4,7,1,3 ]，其中5被3代替了。 按照前面思想，我们可以把数组的元素摆到应该存放的位置，我们想通过排序变为：[1,2,3,4,3,6,7,8,9,10]。除了这个3，其他的都归位。
但是上面的算法就不能直接用了。因为会导致无线循环。 [10,6,9,3,2,8,4,7,1,3 ] //a[0]!=1。把10和3交换 [1, 4,3,3,2,6,7,8,9,10] //7已经归位。a[1]!=1。4和3交换。 [1, 3,3,4,2,6,7,8,9,10] //4已经归位。a[1]!=2，3和3交换。 [1, 3,3,4,2,6,7,8,9,10] //交换之后，a[1]还是3,不是2。继续交换。。。最后导致无限循环
导致无限循环的原因是，有相同的元素。当两个交换的元素相同时，交换之后不变。这样就会一直交换下去。
所以要在代码中加入一个判断，当交换的两个元素值相等时，就不交换了。
【代码】
【结果】
【其他情况一】 如果一个数字重复出现几次，也不影响。 比如，5和8都被3替换了，排序后除了5,8，其他也能归位。
【其他情况二】 如果被不止一个数字代替了，也不影响。 比如5,7,8被3和4代替了，其他数字也能归位。
三、只对符合要求的数字排序 我们进一步延伸一下，如果数组为： [-3,2,5,6,-9,0,7,-3,8,10] 我们能不能得到：[?,2,?,?,5,6,7,8,?,10]
只要在while中写明条件即可。
【代码】
【结果】
【延伸】 对于上面的数组，我只想让6,7,8归位。其他不管。 只要控制条件即可。
|