V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lqw3030
V2EX  ›  LeetCode

菜鸡又来问 leetcode 题目了

  •  
  •   lqw3030 · 2019-01-03 22:38:35 +08:00 · 12348 次点击
    这是一个创建于 1912 天前的主题,其中的信息可能已经有所发展或是发生改变。

    请教大家个问题 这题: Fo59Ld.png

    这个是排行前几的解法

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

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

    29 条回复    2019-01-09 16:08:43 +08:00
    northisland
        1
    northisland  
       2019-01-03 23:13:23 +08:00
    肯定不对,举个简单的反例就可证明。
    {3, 1, 3}

    有高手解答么?
    我只能想到排序后,从前往后遍历,
    或者可穷举时用桶排序,桶>2 立即停止。
    cheniousl
        2
    cheniousl  
       2019-01-03 23:20:15 +08:00 via Android
    解法没问题啊,你不明白的点在哪?
    你的例子里,外层第二次循环,i=2 的 88 就和内层第二次循环 i=0 的 88 重复,直接 false 了
    cheniousl
        3
    cheniousl  
       2019-01-03 23:21:11 +08:00 via Android
    哦,重复返回的是 true
    maninfog
        4
    maninfog  
       2019-01-03 23:50:37 +08:00 via iPhone
    这个解法明显有问题嘛,就你举的这个例子就通不过,这种题我就只想用 hashset 哈哈哈
    Biwood
        5
    Biwood  
       2019-01-04 00:26:53 +08:00
    这函数写的莫名其妙,为啥要写个 if (nums[i] > nums[j]),直接等于号返回 true,末尾返回 false 不就完了吗。
    用了两层遍历,复杂度为 n²,应该还能优化。
    lqw3030
        6
    lqw3030  
    OP
       2019-01-04 00:29:52 +08:00 via iPhone
    @Biwood 这题的最快速度解法就是这个,我就是不理解,而且用我举例的那个数组跑就不通过
    lqw3030
        7
    lqw3030  
    OP
       2019-01-04 00:30:49 +08:00 via iPhone
    @maninfog 哈哈哈,我第一个想法也是 hashSet
    sunnyadamm
        8
    sunnyadamm  
       2019-01-04 00:32:43 +08:00
    双层嵌套,遍历数组有无与第一层相等值,有就直接返回 true,然后终止循环。否则开始第二次循环。很简单的逻辑,当然还有其他方法解答
    lqw3030
        9
    lqw3030  
    OP
       2019-01-04 00:35:38 +08:00 via iPhone
    @northisland 我在答案里看到这种解法,Arrays.sort 然后 for 一次,就是不理解我发的这个解法,而且前三个好像都这个思路
    mainlong
        10
    mainlong  
       2019-01-04 00:37:11 +08:00 via Android   ❤️ 1
    我想了一个解法,大家看看有没有问题。

    Python 有个类型是集合 set,把数组作为参数传给集合,再对比数组元素个数和集合元素个数就行了。不同说明有重复被删掉了。
    sunnyadamm
        11
    sunnyadamm  
       2019-01-04 00:40:18 +08:00
    楼主意思是 9 比 88 小,代码写的是 nums[i] > nums[j],这里有疑问吗?代码在 if 里面,9 比 88 小这种情况不符合 if 和 elseif 的条件,if 及 elif 语句不执行,for 循环继续呀,没毛病。
    Xs0ul
        12
    Xs0ul  
       2019-01-04 00:45:48 +08:00
    如果 int 范围有限,而数组很长(接近 int 总数量),就直接 bitmap

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

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

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

    每种方法的优缺点,空间时间复杂度都可以和面试官讨论
    SingeeKing
        13
    SingeeKing  
       2019-01-04 01:06:59 +08:00
    我第一反应:return len(nums) == len(set(nums))
    hzwjz
        14
    hzwjz  
       2019-01-04 01:35:58 +08:00 via Android
    @SingeeKing 简单优雅。
    hzwjz
        15
    hzwjz  
       2019-01-04 01:38:22 +08:00 via Android
    还有一种 nlogn 的解法就是数组排序后二分查找。

    再有一种就是去重,然后返回去重后的新数组,接着比长度。

    以上这两种本质上都依赖于双指针。
    binux
        16
    binux  
       2019-01-04 01:45:10 +08:00
    因为数据弱?
    WildCat
        17
    WildCat  
       2019-01-04 06:14:17 +08:00 via iPhone
    @Biwood 哇,这个 n^2 怎么打印出来的?
    lqw3030
        18
    lqw3030  
    OP
       2019-01-04 07:06:53 +08:00 via iPhone
    @sunnyadamm,重复输出 true,然而照他这样的算法输出了 false,和预期不一致
    bestkayle
        19
    bestkayle  
       2019-01-04 08:02:29 +08:00 via iPhone
    @lqw3030 #6 最快的解法肯定不是这个,我到公司看看,双层 for 循环太慢了
    ingin
        20
    ingin  
       2019-01-04 08:17:48 +08:00 via Android
    @SingeeKing 很明显你错喽
    renyijiu
        21
    renyijiu  
       2019-01-04 08:54:25 +08:00 via Android
    感觉这个解法是数组排序了,自己想法空间换时间,用 hash 存值判断存在
    bestkayle
        22
    bestkayle  
       2019-01-04 09:50:06 +08:00
    试了下用 go 字典插入判断耗时 28ms
    ColinWang
        23
    ColinWang  
       2019-01-04 10:29:50 +08:00
    位图法,O(n)的时间复杂度
    Biwood
        24
    Biwood  
       2019-01-04 12:00:21 +08:00 via Android   ❤️ 1
    @WildCat PC 版搜狗输入法,输入“ pingfang ”就有二次方的上标了
    MisakaTang
        25
    MisakaTang  
       2019-01-04 12:24:06 +08:00
    就是测试用例太弱被卡过去了,不加 break 是 LTE 但是那组数据是顺序的,加了这个 break 卡掉了这组数据,应该是这样
    SingeeKing
        26
    SingeeKing  
       2019-01-04 19:50:33 +08:00
    @ingin #20 哪里错了。。。
    ingin
        27
    ingin  
       2019-01-05 00:41:51 +08:00 via Android
    @SingeeKing ==换成!=
    SingeeKing
        28
    SingeeKing  
       2019-01-05 01:08:49 +08:00
    @ingin #27 额。。这就尴尬了
    Tidycc
        29
    Tidycc  
       2019-01-09 16:08:43 +08:00
    不是很懂那个 `nums[i] > nums[j]` 的用法,又不是有序数组。感觉还是使用 HashSet,看长度是否变短。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2673 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 15:27 · PVG 23:27 · LAX 08:27 · JFK 11:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.