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

菜鸡又来问 leetcode 题目了

  •  
  •   lqw3030 · 257 天前 · 9805 次点击
    这是一个创建于 257 天前的主题,其中的信息可能已经有所发展或是发生改变。

    请教大家个问题 这题: 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
        1
    northisland   257 天前
    肯定不对,举个简单的反例就可证明。
    {3, 1, 3}

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

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

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

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

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

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

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

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