贵阳企业网站建设制作,怎么模仿别人做网站,园林景观设计公司需要什么资质,给公司做网站 优帮云【问题描述】[中等]
给定一个包含 n 1 个整数的数组 nums#xff0c;其数字都在 1 到 n 之间#xff08;包括 1 和 n#xff09;#xff0c;可知至少存在一个重复的整数。假设只有一个重复的整数#xff0c;找出这个重复的数。输入: [1,3,4,2,2]
输出: 2说明#xff1a…【问题描述】[中等]
给定一个包含 n 1 个整数的数组 nums其数字都在 1 到 n 之间包括 1 和 n可知至少存在一个重复的整数。假设只有一个重复的整数找出这个重复的数。输入: [1,3,4,2,2]
输出: 2说明不能更改原数组假设数组是只读的。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字但它可能不止重复出现一次。来源力扣LeetCode
链接https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。【解答思路】
1. 排序法不符合题意
时间复杂度O(N) 空间复杂度O(1)
public int findDuplicate(int[] nums) {Arrays.sort(nums);for (int i 0; i nums.length - 1; i) {if (nums[i] nums[i 1]) {return nums[i];}}return -1;
}
2. HashSet 不符合题意
时间复杂度O(N) 空间复杂度O(N)
public int findDuplicate(int[] nums) {HashSetInteger set new HashSet();for (int i 0; i nums.length - 1; i) {if (set.contains(nums[i])) {return nums[i];}else{set.add(nums[i]);}}return -1;
}3.二分查找符合题意 时间复杂度O(NlogN) 空间复杂度O(1)
public class Solution {public int findDuplicate(int[] nums) {int len nums.length;int left 1;int right len - 1;while (left right) {// 在 Java 里可以这么用当 left right 溢出的时候无符号右移保证结果依然正确int mid (left right) 1;int cnt 0;for (int num : nums) {if (num mid) {cnt 1;}}// 根据抽屉原理小于等于 4 的个数如果严格大于 4 个// 此时重复元素一定出现在 [1, 4] 区间里if (cnt mid) {// 重复元素位于区间 [left, mid]right mid;} else {// if 分析正确了以后else 搜索的区间就是 if 的反面// [mid 1, right]left mid 1;}}return left;}
}
4. 双指针技巧型 符合体题意 时间复杂度O(N) 空间复杂度O(1)
public int findDuplicate(int[] nums) {int slow nums[0];int fast nums[nums[0]];//寻找相遇点while (slow ! fast) {slow nums[slow];fast nums[nums[fast]];}//slow 从起点出发, fast 从相遇点出发, 一次走一步slow 0;while (slow ! fast) {slow nums[slow];fast nums[fast];}return slow;
}
5.二进制不一定符合题意
比较1到n和nums各位二进制“1”的数量nums多出来的1的组合就是重复数组 时间复杂度O(N) 空间复杂度O(1)
public int findDuplicate(int[] nums) {int res 0;int n nums.length; //统计每一列 1 的个数for (int i 0; i 32; i) {int a 0;int b 0;int mask (1 i);for (int j 0; j n; j) {//统计原数组当前列 1 的个数if ((nums[j] mask) 0) {a;}//统计 1 到 n 序列中当前列 1 的个数if ((j mask) 0) {b;}}if (a b) {res res | mask;}}return res;
}
【总结】
1.二分法查找有序数组 还可以用于确定一个有范围的整数
2.二分查找经验先搞懂思路再研究细节多做问题去应用
把定义区间成为左闭右闭区间左右边界是无差别的弄成左闭右开反而增加了思考的复杂程度明确 int left ( right - left ) / 2 这里除以 2 是下取整明确 while(left right) 和 while(left right) 这两种写法其实在思路上有本质差别 while(left right) 在循环体内部直接查找元素而 while(left right) 在循环体内部一直在排除元素第 2 种思路在解决复杂问题的时候可以使得问题变得简单始终在思考下一轮搜索区间是什么把它作为注释写到代码里面就能帮助我们搞清楚边界是不是能取到等于、1 、-1 之类的细节思考清楚每一行代码背后的语义是什么保证语义上清晰也是写对代码减少 bug 的一个非常有效的策略。
3. 快慢指针 链表 数组特定条件
转载链接https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by–52/
参考链接https://leetcode-cn.com/problems/find-the-duplicate-number/solution/er-fen-fa-si-lu-ji-dai-ma-python-by-liweiwei1419/
快慢指针动画参考链接https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
