645、448、442 一个数组的元素为1~n,其中有的数被其他的数代替了,找出这些数
645 一个数组的元素为1~n,其中一个数被另一个数代替了,找出这两个数 点击此处返回总目录 448 一个数组的元素是1~n,其中若干个数被其他数代替了,找出这若干个数 442 一个数组的元素为1~n,其中若干个数被其他数代替了,找出这若干个数被谁替代了
一、645 一个数组的元素为1~n,其中一个数被另一个数代替了,找出这两个数
【题目】
【方法一】 最直接的想法就是,搞一个Set,每次存的时候检查一下是否已经存在这个元素了。找到重复的 ^元素之后有一万种方法可以求出是谁替换的它,比如上面的例子中,可以一次查看Set中有没有1234;可以通过数学的方法1+2+3+4 - 1 -2 -2 -4 +2 = 3。还可以通过位运算,(1 ^2 ^ 2 ^ 4) ^ (1^2^3^4) ^ 2 = 3。
代码:
结果:
效率不是很高。
【方法二】 当然也可以搞一个相同大小的数组,起的作用跟Set一样。
代码:
结果:
瞬间快了很多。
【方法三】 我们可以通过一趟或半趟遍历就求出重复的元素,而且不借助辅助空间。 因为nums数组存放的是从1到n的整数。我们可以充分利用符号来表示某个数是否出现过。这样就省去了前面使用Set。 具体的就是,当遍历到一个数x时,就把第x个数变成负的,意思是第x个数出现过一次了。以后再出现x的时候就能知道已经出现过了。
代码:
结果:
【方法四】 利用题目一个数组的元素为1~n,在o(n)的时间内对数组排序 的思想。将元素归位。
因此,本题的代码为:
结果:
二、448 一个数组的元素是1~n,其中若干个数被另外的数代替了,找出这若干个数 【题目】
本来是1.2.3...8。现在5和6被2,3替代了。
【方法一】 同上面方法一,搞一个Set。
代码:
结果:
跟上一个题目一样,效果不怎么好。
【方法二】 同上题方法二,我们该用数组代替Set试一下。创建一个跟nums相同大小的数组arr,初试为0。遍历nums的数,设置arr相应位置为1。最后遍历一遍arr。
代码:
结果:
可以看到,效率瞬间就上来了。 看来使用数组比使用Set要快很多。
【方法三】 我们仍不死心,想要试试不使用额外空间来做。跟上题方法三,一样。通过负号来记录。
代码:
结果:
【方法四】 同上一题的方法四。通过排序让数字归位。
代码:
结果: 按道理应该跟方法三的效率差不多,但是没有跑出来。可能是用数组的人太多了。
三、442 一个数组的元素为1~n,其中若干个数被其他数代替了,找出这若干个数被谁替代了
【题目】
【分析】 这个题跟上面的题目没啥区别。5、6被2、3代替了。上面的题目是输出5、6;这个题目是输出2、3。
【方法一】 使用set。略。效果肯定不咋样。
【方法二】 使用数组。
代码:
结果:
【方法三】 不使用数组,利用负号。
代码:
结果:
方法三肯定比方法二要慢一些。因为方法二用空间换了时间。
【方法四】 同上一题方法四。排序。
代码: 结果:
|