网站开发工具发展史,广州手机网站,摄影网站源码,wordpress主题破解版二分#xff0c;双指针#xff0c;环形链表。
题目 不看完题就是排序后#xff0c;用两个快慢指针移动#xff0c;找到相同就返回即可。
class Solution {public int findDuplicate(int[] nums) {Arrays.sort(nums);int l0;int r1;while(rnums.length){if(nums[l]num…二分双指针环形链表。
题目 不看完题就是排序后用两个快慢指针移动找到相同就返回即可。
class Solution {public int findDuplicate(int[] nums) {Arrays.sort(nums);int l0;int r1;while(rnums.length){if(nums[l]nums[r])return nums[r];l; r;}return -1;}
}但是题要求不修改数组因此肯定不会那么简单。先是二分查找法由题可知nums只有一个重复的数且数字的大小在1到n那么可以直接看nums[i]去遍历每个数值然后用一个计数器去记录i注意假设nums[x]找到了这个数那后面的计数器nums[x1]都是加一的然后二分划分区间没有重复的在左半区重复数后的在右半区重复数就是要找的mid。如果比目标值即重复的数小说明没有跟目标值相等说明刚好一个说明当前没有找到重复的数比目标值大说明就是找到了重复数的区间继续收缩。然后就是二分的模板了注意比较时是比数值不是比索引。
时间复杂度 O(nlogn)空间复杂度 O(1)。
class Solution {public int findDuplicate(int[] nums) {int n nums.length;int l 1, r n - 1, ans -1;while (l r) {int mid (l r) 1;int cnt 0;for (int i 0; i n; i) {if (nums[i] mid) {cnt;}}if (cnt mid) {l mid 1;} else {r mid - 1;ans mid;}}return ans;}
}接着是快慢指针龟兔赛跑算法。这题由于索引跟元素值的限定范围假如按索引指向的数值当作下一个索引如此往复是可以形成一个环的即假设走到某个k1点时指向的数值是k然后去到索引k索引k的数值是k2然后k2的数值又是k如此反复这里是可以形成一个环的而这个k1时就是环的入口点也是要找的重复值。然后用快慢指针慢指针每次走一步快指针每次走两步相遇一次后做标记慢指针归零从新出发快指针从环里出发然后再次相遇即可找到入口点了。慢指针走一步 slow slow.next快指针走两步 fast fast.next.next换成数组就是包多一层即可。注意要排除形成自环即索引的数值是本身因此从零出发可以排除。
时间复杂度 O(n)空间复杂度 O(1)。
class Solution {public int findDuplicate(int[] nums) {int slow 0, fast 0;//初始化是相等的所以先执行第一次相遇找到标记点do {slow nums[slow];fast nums[nums[fast]];} while (slow ! fast);//慢指针重新出发快指针继续在环里走slow 0;while (slow ! fast) {slow nums[slow];fast nums[fast];}return slow;}
}
