一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 589|回复: 10
收起左侧

[算法题] Contains Duplicate II (in Java)-EASY

[复制链接] |试试Instant~ |关注本帖
草袋豆子 发表于 2015-6-12 16:23:58 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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 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 == nums[j]) && (Math.abs(i-j) == k) )
                {
                    return true;
                }
            }
        }
        return false;
    }
}





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

原来如此。。。。
回复 支持 反对

使用道具 举报

love1point 发表于 2015-6-13 09:00:02 | 显示全部楼层
stellari 发表于 2015-6-12 23:41
楼主其实有写 “[ i ]”,但是正好“斜体”的Markup记号也是这个,所以达到的效果是“[ i ]”不显示, ...

这你都知道啊,给你跪了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 22:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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