数组问题(鸽巢原理、数字交换、链表寻环)

2021-02-18 15:17

阅读：572

标签：下标 sys img swa span 比较 style 算法 logs

287. 寻找重复数

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

因为不能能改原来的数组，并且只能使用额外O1的空间，所以我们不能使用map记录，也不能维护一个新的数组

因为时间复杂度要在n2以内，所以暴力查找也是不可取的

因为数据范围在1~n-1，所以可以保证不会数组越界，因此使用链表中快慢指针寻找环算法

https://www.cnblogs.com/fankongkong/p/7007869.html

1、当fast指针仅仅只比slow指针多走一个环，如图所示

技术图片

2、第一次相遇的时候，如图

技术图片

3、这个时候将fast 重新赋值为开头，如图

技术图片

4、再走两次，则找到了环的入口结点

技术图片

重新梳理一下步骤，解题思路

a、第一步，找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，直到fast==slow找到在环中的相汇点。

b、第二步，找环的入口。接上步，当fast==slow时，fast所经过节点数为2x,slow所经过节点数为x,设环中有n个节点，fast比slow多走一圈有2x=n+x; n=x;

可以看出slow实际走了一个环的步数，再让fast指向链表头部，slow位置不变。

假设链表开头到环接口的距离是y，如下图所示，那么x-y表示slow指针走过的除链表开头y在环中走过的距离，那么slow再走y步，此时fast结点与slow结点相遇，fast == slow ，x-y+y=x = n，即此时slow指向环的入口。

技术图片

442. 数组中重复的数据

比较好的解法是鸽巢原理+亦或交换数据

不用到任何额外空间并在O(n)时间复杂度

把大小为i的数字，放进下标为i-1的位置上，排完之后还剩下的位置不对的，就是多余的。

对第i位置上的数字k，因为k！=i-1，所以要把k丢到k-1的位置上，然后再看看换过来的数字是不是i-1，不是就继续换（有点像排序算法），当这个位置正确后，就进入下一个位置。

当所有位置处理完以后，再扫一遍，发现位置和数字不匹配的数字就是多余的数字，因为不能采用额外空间，所以使用无额外内存的亦或交换（加减交换也可以）。

public List findDuplicates(int[] nums) {
            Set res=new HashSet();
            for(int i=0;i(res);
        }
        public void  swap(int[] nums,int a,int b){
            nums[a]^=nums[b];
            nums[b]^=nums[a];
            nums[a]^=nums[b];
        }

数组问题(鸽巢原理、数字交换、链表寻环)

标签：下标 sys img swa span 比较 style 算法 logs

原文地址：https://www.cnblogs.com/wjune-0405/p/12690872.html

上一篇：JavaScript中的构造函数

下一篇：Python面试合集史上最全面Python面试题和详解(10套) 完整版

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：数组问题(鸽巢原理、数字交换、链表寻环)
文章链接：http://soscw.com/index.php/essay/57095.html

亲，登录后才可以留言！

数组问题(鸽巢原理、数字交换、链表寻环)

287. 寻找重复数

https://www.cnblogs.com/fankongkong/p/7007869.html

442. 数组中重复的数据

评论

热门文章

推荐文章

最新文章

置顶文章