📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1951| 回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

Contains Duplicate II (in Java)-EASY

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
原题地址:https://leetcode.com/problems/contains-duplicate-ii/

题目:
Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums = nums[j] and the difference between [i]iand j is at most k.


我的Code:
public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k)
    {
        int arrayLength = nums.length;
        
        for (int i = 0; i < arrayLength - 1; i++)
        {
            for (int j = i + 1; j < arrayLength; j++)
            {
                if ( (nums[i] == nums[j]) && (Math.abs(i-j) == k) )
                {
                    return true;
                }
            }
        }
        return false;
    }
}





我点击“submit”后,系统提示“Time Limit Exceeded”。 我测试过我的code,可以用,不知道为什么在这里就无法使用。
希望大家帮忙看一下。非常感谢!

上一篇:请问各位大神手头有 java se 7 programmer 1 的测试题吗
下一篇:HashMap小盲区
🔗
love1point 2015-6-12 17:04:24 | 只看该作者
全局:
1, 题目要求 nums[i] == nums[j]
2. Math.abs(i, j) < = k ?
回复

使用道具 举报

🔗
stellari 2015-6-12 17:04:31 | 只看该作者
全局:
你这是O(N^2)的算法,必然过不了最后的大数据测试用例。你需要找一个O(N)的算法。
回复

使用道具 举报

🔗
love1point 2015-6-12 17:16:18 | 只看该作者
全局:
这题可以用HashMap,key 是 元素,value是元素对应的index。
  1. public class Solution {
  2.     public boolean containsNearbyDuplicate(int[] nums, int k) {
  3.         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  4.         int min = Integer.MAX_VALUE;
  5.         
  6.         for(int i =0; i < nums.length; i++)
  7.         {
  8.             if(map.containsKey(nums[i]))
  9.             {
  10.                 int index = map.get(nums[i]);
  11.                 int diff = i - index;
  12.                 min = Math.min(min, diff);
  13.             }
  14.             map.put(nums[i], i);
  15.         }
  16.         if(min <= k)
  17.         {
  18.             return true;
  19.         }
  20.         else
  21.         {
  22.             return false;
  23.         }
  24.     }
  25. }
复制代码
回复

使用道具 举报

🔗
 楼主| 草袋豆子 2015-6-12 17:34:32 | 只看该作者
全局:
love1point 发表于 2015-6-12 17:04
1, 题目要求 nums == nums[j]
2. Math.abs(i, j) < = k ?

对。
nums[i] == nums[j]

Math.abs(i, j) <= k (At most k). 关于这个条件,我就默认它们相减结果是等于k的。
回复

使用道具 举报

🔗
 楼主| 草袋豆子 2015-6-12 17:35:34 | 只看该作者
全局:
stellari 发表于 2015-6-12 17:04
你这是O(N^2)的算法,必然过不了最后的大数据测试用例。你需要找一个O(N)的算法。

我的JAVA基础比较弱……能请问一下你说的O(N)算法是什么吗?

说到大数据测试,我确实看到网站上用了一个非常长的array来测试我的code。
回复

使用道具 举报

🔗
cloudending 2015-6-12 20:24:34 | 只看该作者
全局:

nums是数组,怎么能跟nums[j]比较呢,怎么比都是错的呀
小于等于k的话意思是说只要abs(i-j) <=k就符合条件,不一定要等于k
回复

使用道具 举报

🔗
raymanhjn 2015-6-12 21:10:49 | 只看该作者
全局:
同新手,O(N)不是算法,是算法的时间复杂度 暂且你就当你程序的两个for需要执行n^2次才能找到结果,而O(N)只需要N次就找到了,加油哈!
回复

使用道具 举报

🔗
stellari 2015-6-12 23:41:45 | 只看该作者
全局:
cloudending 发表于 2015-6-12 20:24
nums是数组,怎么能跟nums[j]比较呢,怎么比都是错的呀
小于等于k的话意思是说只要abs(i-j)


楼主其实有写 “[ i ]”,但是正好“斜体”的Markup记号也是这个,所以达到的效果是“[ i ]”不显示,而其后的所有文字都变成了斜体。
回复

使用道具 举报

🔗
cloudending 2015-6-13 08:49:41 | 只看该作者
全局:
stellari 发表于 2015-6-12 23:41
楼主其实有写 “[ i ]”,但是正好“斜体”的Markup记号也是这个,所以达到的效果是“[ i ]”不显示, ...

原来如此。。。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表