这是一个创建于 2483 天前的主题，其中的信息可能已经有所发展或是发生改变。
请教大家个问题 这题： 
这个是排行前几的解法
public boolean containsDuplicate(int[] nums) { for (int i = 1 i < nums.length; i++) { for (int j = i - 1; j >= 0; j--) { if (nums[i] > nums[j]) { break; } else if (nums[i] == nums[j]) { return true; } } } return false; } 有没有朋友给我讲解下这么写的思路，这种解法如果输入
int[] nums = {88, 9, 88, 1, 88, 5, 88, 3, 88 }; 不是返回的就不正确了吗？还是我没理解题目
 | 1 northisland 2019-01-03 23:13:23 +08:00 肯定不对，举个简单的反例就可证明。 {3, 1, 3} 有高手解答么？ 我只能想到排序后，从前往后遍历， 或者可穷举时用桶排序，桶>2 立即停止。 |
 | 2 cheniousl 2019-01-03 23:20:15 +08:00 via Android 解法没问题啊，你不明白的点在哪？ 你的例子里，外层第二次循环，i=2 的 88 就和内层第二次循环 i=0 的 88 重复，直接 false 了 |
| 3 cheniousl 2019-01-03 23:21:11 +08:00 via Android 哦，重复返回的是 true |
 | 4 maninfog 2019-01-03 23:50:37 +08:00 via iPhone 这个解法明显有问题嘛，就你举的这个例子就通不过，这种题我就只想用 hashset 哈哈哈 |
 | 5 Biwood 2019-01-04 00:26:53 +08:00 这函数写的莫名其妙，为啥要写个 if (nums[i] > nums[j])，直接等于号返回 true，末尾返回 false 不就完了吗。 用了两层遍历，复杂度为 n，应该还能优化。 |
 | 8 sunnyadamm 2019-01-04 00:32:43 +08:00 双层嵌套，遍历数组有无与第一层相等值，有就直接返回 true，然后终止循环。否则开始第二次循环。很简单的逻辑，当然还有其他方法解答 |
 | 9 xyooyx OP @northisland 我在答案里看到这种解法，Arrays.sort 然后 for 一次，就是不理解我发的这个解法，而且前三个好像都这个思路 |
 | 10 mainlong 2019-01-04 00:37:11 +08:00 via Android  1 我想了一个解法，大家看看有没有问题。 Python 有个类型是集合 set，把数组作为参数传给集合，再对比数组元素个数和集合元素个数就行了。不同说明有重复被删掉了。 |
| 11 sunnyadamm 2019-01-04 00:40:18 +08:00 楼主意思是 9 比 88 小，代码写的是 nums[i] > nums[j]，这里有疑问吗？代码在 if 里面，9 比 88 小这种情况不符合 if 和 elseif 的条件，if 及 elif 语句不执行，for 循环继续呀，没毛病。 |
 | 12 Xs0ul 2019-01-04 00:45:48 +08:00 如果 int 范围有限，而数组很长（接近 int 总数量），就直接 bitmap 如果数组相对短，就自己做一个简单的 hashset，比如除 1000 取余数，1000 这个数的大小取决于 int 范围和数组长度 如果数组特别短，可以直接排序或者二叉搜索树 甚至可以先扫一遍了解数据分布 每种方法的优缺点，空间时间复杂度都可以和面试官讨论 |
 | 13 SingeeKing PRO 我第一反应：return len(nums) == len(set(nums)) |
 | 14 hzwjz 2019-01-04 01:35:58 +08:00 via Android @SingeeKing 简单优雅。 |
| 15 hzwjz 2019-01-04 01:38:22 +08:00 via Android 还有一种 nlogn 的解法就是数组排序后二分查找。 再有一种就是去重，然后返回去重后的新数组，接着比长度。 以上这两种本质上都依赖于双指针。 |
 | 16 binux 2019-01-04 01:45:10 +08:00 因为数据弱？ |
| 18 xyooyx OP @sunnyadamm，重复输出 true，然而照他这样的算法输出了 false，和预期不一致 |
 | 19 KgM4gLtF0shViDH3 2019-01-04 08:02:29 +08:00 via iPhone @lqw3030 #6 最快的解法肯定不是这个，我到公司看看，双层 for 循环太慢了 |
 | 20 ingin 2019-01-04 08:17:48 +08:00 via Android @SingeeKing 很明显你错喽 |
 | 21 renyijiu 2019-01-04 08:54:25 +08:00 via Android 感觉这个解法是数组排序了，自己想法空间换时间，用 hash 存值判断存在 |
| 22 KgM4gLtF0shViDH3 2019-01-04 09:50:06 +08:00 试了下用 go 字典插入判断耗时 28ms |
 | 23 ColinWang 2019-01-04 10:29:50 +08:00 位图法，O(n)的时间复杂度 |
 | 25 MisakaTang 2019-01-04 12:24:06 +08:00 就是测试用例太弱被卡过去了,不加 break 是 LTE 但是那组数据是顺序的,加了这个 break 卡掉了这组数据,应该是这样 |
| 26 SingeeKing PRO @ingin #20 哪里错了。。。 |
| 27 ingin 2019-01-05 00:41:51 +08:00 via Android @SingeeKing ==换成！= |
| 28 SingeeKing PRO @ingin #27 额。。这就尴尬了 |
 | 29 Tidycc 2019-01-09 16:08:43 +08:00 不是很懂那个 `nums[i] > nums[j]` 的用法，又不是有序数组。感觉还是使用 HashSet，看长度是否变短。 |
Select Language