菜鸡又来问 leetcode 题目了

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2184 天前的主题，其中的信息可能已经有所发展或是发生改变。

请教大家个问题这题：

这个是排行前几的解法



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 };

不是返回的就不正确了吗？还是我没理解题目

nums

int

解法

return

29 条回复 • 2019-01-09 16:08:43 +08:00

northisland

2019-01-03 23:13:23 +08:00

肯定不对，举个简单的反例就可证明。
{3, 1, 3}

有高手解答么？
我只能想到排序后，从前往后遍历，
或者可穷举时用桶排序，桶>2 立即停止。

cheniousl

2019-01-03 23:20:15 +08:00 via Android

解法没问题啊，你不明白的点在哪？
你的例子里，外层第二次循环，i=2 的 88 就和内层第二次循环 i=0 的 88 重复，直接 false 了

cheniousl

2019-01-03 23:21:11 +08:00 via Android

哦，重复返回的是 true

maninfog

2019-01-03 23:50:37 +08:00 via iPhone

这个解法明显有问题嘛，就你举的这个例子就通不过，这种题我就只想用 hashset 哈哈哈

Biwood

2019-01-04 00:26:53 +08:00

这函数写的莫名其妙，为啥要写个 if (nums[i] > nums[j])，直接等于号返回 true，末尾返回 false 不就完了吗。
用了两层遍历，复杂度为 n²，应该还能优化。

lqw3030

2019-01-04 00:29:52 +08:00 via iPhone

@Biwood 这题的最快速度解法就是这个，我就是不理解，而且用我举例的那个数组跑就不通过

lqw3030

2019-01-04 00:30:49 +08:00 via iPhone

@maninfog 哈哈哈，我第一个想法也是 hashSet

sunnyadamm

2019-01-04 00:32:43 +08:00

双层嵌套，遍历数组有无与第一层相等值，有就直接返回 true，然后终止循环。否则开始第二次循环。很简单的逻辑，当然还有其他方法解答

lqw3030

2019-01-04 00:35:38 +08:00 via iPhone

@northisland 我在答案里看到这种解法，Arrays.sort 然后 for 一次，就是不理解我发的这个解法，而且前三个好像都这个思路

mainlong

2019-01-04 00:37:11 +08:00 via Android

我想了一个解法，大家看看有没有问题。

Python 有个类型是集合 set，把数组作为参数传给集合，再对比数组元素个数和集合元素个数就行了。不同说明有重复被删掉了。

sunnyadamm

2019-01-04 00:40:18 +08:00

楼主意思是 9 比 88 小，代码写的是 nums[i] > nums[j]，这里有疑问吗？代码在 if 里面，9 比 88 小这种情况不符合 if 和 elseif 的条件，if 及 elif 语句不执行，for 循环继续呀，没毛病。

Xs0ul

2019-01-04 00:45:48 +08:00

如果 int 范围有限，而数组很长（接近 int 总数量），就直接 bitmap

如果数组相对短，就自己做一个简单的 hashset，比如除 1000 取余数，1000 这个数的大小取决于 int 范围和数组长度

如果数组特别短，可以直接排序或者二叉搜索树

甚至可以先扫一遍了解数据分布

每种方法的优缺点，空间时间复杂度都可以和面试官讨论