前言:
今天朋友们对“输出数组里的数字”都比较讲究,我们都需要知道一些“输出数组里的数字”的相关文章。那么小编也在网摘上汇集了一些有关“输出数组里的数字””的相关知识,希望朋友们能喜欢,各位老铁们快快来学习一下吧!问题
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例1
输入:[2, 3, 1, 0, 2, 5, 3]
输出:2或者3
解法一思路:排序+遍历首先对数据排序,排序完成后遍历数据,如果遇到相同的数据,立即返回。时间复杂度O(nlogn),空间复杂度O(logn)具体实现:java
class Solution { public int findRepeatNumber(int[] nums) { Arrays.sort(nums); int compare = nums[0]; for (int i = 1; i < nums.length; i++) { if (compare == nums[i]) { return compare; } else { compare = nums[i]; } } return -1; }}解法二思路: hash表遍历数组,将数据作为hash表的key,个数作为value如果发现有一个key已经存在直接返回数据时间复杂度O(n),空间复杂度O(n)具体实现:java
class Solution { public int findRepeatNumber(int[] nums) { HashMap<Integer,Integer> map = new HashMap<>(nums.length); for(int i = 0;i<nums.length;i++){ if(map.get(nums[i])==null){ map.put(nums[i],1); } else{ return nums[i]; } } return -1; }}解法三思路:冲突法分析:
可以知道所有数字都在0~n-1的范围内,那么我们可以知道:如果完全不冲突,必然0-n-1每个数一个,那么我们可以将数组下表作为key,必然有key是重复的。找到这个重复的key就好了
遍历数组,将数据放在对应的下标。如果下标冲突,则返回数据,如果不冲突,则与当前数据交换位置比如:[2, 3, 1, 0, 2, 5, 3]第一次:[1,3,2,0,2,5,3]第二次:[3,1,2,0,2,5,3]第三次:[0,1,2,3,2,5,3]第四次,2冲突了,直接返回2时间复杂度O(n),空间复杂度O(1)
class Solution { public int findRepeatNumber(int[] nums) { for (int i = 0; i < nums.length; ) { if (i==nums[i]){ i++; continue; } if (nums[nums[i]] == nums[i]) { return nums[i]; } else { int t = nums[i]; nums[i] = nums[t]; nums[t] = t; } } return -1; }}问题变更一
如果需要找出全部的相同的数字,上面的方法还有效吗?
全部可以实现(建议自行尝试)问题变更二
在一个长度为n+1的数组里的所有数字都在1~n范围内,所以数组种至少有一个数字是重复的。请找出数组种任意一个重复的数字,但不能修改输入的数组。
解法一思路:复制数组首先将数组复制下来。然后利用原问题种的任意一种解法
代码参考以上
解法二思路:二分查找的思想分析:
我们把1-n的数字从中间的数字m分为两部分,前面一般为1-m,后面一般为m+1-n。如果1-m的数字的数目超过了m,那么这一版的区间里面一定包含重复的数字;如果两个区间都相等,那么将m的位置前移一位,再进行比较。以此为思想
比如数组 [1,2,2,4,5]第一次比较:m为3; 1-3和4-5分别有3个和2个。无法辨别,移动m=2第二次比较:m为2;1-2和3-5分别有3个和2个。区间1-2中一定有重复的数字第三次比较:m为1;1为1次,2为2次。重复数字为2时间复杂度O(nlogn),空间复杂度O(1)
public int findRepeatNumber(int[] nums){ if (null == nums || nums.length == 0 || nums.length == 1) { return -1; } int left = 1; int right = nums.length; int mid = left + (right - left) / 2; while (left <= right) { int preNums = mid - left + 1; int pre = countRange(nums ,left, mid); if (pre == preNums) { mid = mid - 1; //边界值 if (mid < left){ mid = left + (right - left) / 2; left = mid + 1; mid = left + (right - left) / 2; } } else if (pre < preNums) { if (left == right) { return left; } left = mid + 1; mid = left + (right - left) / 2; } else { if (left == right) { return left; } right = mid; mid = left + (right - left) / 2; } } return -1; }
参考:二分查找
标签: #输出数组里的数字