找出数组中重复的数字。
在一个长度为 n n n 的数组 nums 里的所有数字都在 0 ~ n − 1 0~n-1 0~n−1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入: [2, 3, 1, 0, 2, 5, 3] 输出:2 或 3解法一:排序 思路
排序后重复的元素会扎堆在一起,然后遍历一遍即可。
复杂度时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)。排序。
空间复杂度: O ( 1 ) O(1) O(1)。原地堆排。
代码int findRepeatNumber(int[] nums) { int n = nums.length; Arrays.sort(nums); for (int i = 1; i < n; i++) { if (nums[i] == nums[i - 1]) { return nums[i]; } } return -1; }解法二:HashSet 思路
利用 HashSet 去重的特性,将数组元素加入 Set 前先判是否在 Set 中,如果 Set 中存在就说明重复了。
复杂度时间复杂度: O ( n ) O(n) O(n)。遍历数组所有元素。
空间复杂度: O ( n ) O(n) O(n)。Set 最大容纳 n 个元素。
代码int findRepeatNumber(int[] nums) { int n = nums.length; HashSet解法三:原地置换(最优解) 思路s = new HashSet<>(); for (int i = 0; i < n; i++) { if(s.contains(nums[i])) { return nums[i]; } s.add(nums[i]); } return -1; }
将元素放在对应元素下标的元素中,当发现要放的位置与当前元素相同时,则说明坑位被占领,即元素重复。
复杂度时间复杂度: O ( n ) O(n) O(n)。遍历数组所有元素。
空间复杂度: O ( 1 ) O(1) O(1)。在原数组上置换。
代码int findRepeatNumber(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { while (nums[i] != i) { if (nums[nums[i]] == nums[i]) { return nums[i]; } swap(nums, i, nums[i]); } } return -1; } void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }287. 寻找重复数
给定一个包含 n + 1 n + 1 n+1 个整数的数组 nums ,其数字都在 1 ~ n 1 ~ n 1~n 之间(包括 1 和 n),nums 有且只有一个重复的整数 ,找出 这个重复的数 。
你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
示例 1:
输入:nums = [1,3,4,2,2] 输出:2
示例 2:
输入:nums = [3,1,3,4,2] 输出:3解法一:Floyd 判环法(最优解) 思路
这题与上一题的最大不同是,限制了 nums 中只有一个重复的整数。
把数组下标看成节点 A,那么对应下标上的元素则是节点 A 指向的下一个节点。按照此法定义,不难得出数组构成一个环。
如:[1,3,4,2,2]
如:[3,1,3,4,2]
从图中不难发现,重复节点即入口节点。所以原问题转换为寻找环的入口节点,也就是 141. 环形链表 II 。
复杂度时间复杂度: O ( n ) O(n) O(n)。遍历数组所有元素。
空间复杂度: O ( 1 ) O(1) O(1)。只需两个常量。
代码int findDuplicate(int[] nums) { int l = 0, r = 0; while (true) { l = nums[l]; r = nums[nums[r]]; if (l == r) break; } r = 0; while (true) { l = nums[l]; r = nums[r]; if (l == r) return l; } }141. 环形链表
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
不允许修改链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。思路
- 慢指针走一步,快指针走两步,直到碰撞。
- 当第一次碰撞时,说明该链表存在环。
时间复杂度: O ( n ) O(n) O(n)。遍历链表所有元素。
空间复杂度: O ( 1 ) O(1) O(1)。只需两个常量。
代码boolean hasCycle(ListNode head) { ListNode l = head, r = head; while (true) { if (r == null || r.next == null) return false; l = l.next; r = r.next.next; if (l == r) break; } return true; }142. 环形链表 II
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
不允许修改链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1 输出:返回索引为 1 的链表节点 解释:链表中有一个环,其尾部连接到第二个节点。解法一:Floyd 判环法(最优解) 思路
- 慢指针走一步,快指针走两步,直到碰撞。
- 当第一次碰撞时,说明该链表存在环。
- 快指针返回到原点,快慢指针同时走一步,直到再次碰撞。
- 当第二次碰撞时,所指向的节点就是入口节点。
时间复杂度: O ( n ) O(n) O(n)。遍历链表所有元素。
空间复杂度: O ( 1 ) O(1) O(1)。只需两个常量。
代码ListNode detectCycle(ListNode head) { ListNode l = head, r = head; while (true) { if (r == null || r.next == null) return null; l = l.next; r = r.next.next; if (l == r) break; } r = head; while (l != r) { l = l.next; r = r.next; } return l; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)