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

有大佬解释一下这代码什么原理吗

  •  
  •   stevenbipt · 2018-04-05 22:59:25 +08:00 · 3875 次点击
    这是一个创建于 2184 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刷 leetcode 时翻了一下以前刷的题发现一个神奇的代码,题目是 leetcode 第一题两数之和,本来以为用 hash 表做已经达到极限了,结果发现了一个更快的代码,由于个人能力有限分析不出全部代码的精明之处,求大佬们指点。 java 代码: class Solution { public int[] twoSum(int[] nums, int target) { int numMin = Integer.MAX_VALUE; int numMax = Integer.MIN_VALUE; for (int num : nums) { if (num < numMin) { numMin = num; }

        if (num > numMax) {
          numMax = num;
        }
      }  
      int max = target - numMin;
      int min = target - numMax;
    
      int targetMax = max > numMax ? numMax : max;
      int targetMin = min < numMin ? numMin : min;  
      int[] numIndices = new int[targetMax - targetMin + 1];
    
      for (int i = 0; i <= numIndices.length - 1; i++) {
        numIndices[i] = -1;
      }    
      for (int i = 0; i <= nums.length - 1; i++) {
        if (nums[i] >= targetMin && nums[i] <= targetMax) {
          int offset = -targetMin;
          if (numIndices[(target - nums[i]) + offset] != -1) {
            return new int[] { numIndices[(target - nums[i]) + offset], i };
          } else {
            numIndices[nums[i] + offset] = i;
          }
        }
      }
      return new int[] { 0, 0 };
    }
    

    }

    15 条回复    2018-04-06 08:07:43 +08:00
    pandaaa
        1
    pandaaa  
       2018-04-05 23:04:23 +08:00 via Android   ❤️ 1
    排版啊少年→_→
    stevenbipt
        2
    stevenbipt  
    OP
       2018-04-05 23:06:29 +08:00
    @pandaaa 没搞懂这个代码怎么排版出来的= =
    stevenbipt
        3
    stevenbipt  
    OP
       2018-04-05 23:07:31 +08:00
    class Solution {
    public int[] twoSum(int[] nums, int target) {

    int numMin = Integer.MAX_VALUE;
    int numMax = Integer.MIN_VALUE;
    for (int num : nums) {
    if (num < numMin) {
    numMin = num;
    }

    if (num > numMax) {
    numMax = num;
    }
    }
    int max = target - numMin;
    int min = target - numMax;

    int targetMax = max > numMax ? numMax : max;
    int targetMin = min < numMin ? numMin : min;

    int[] numIndices = new int[targetMax - targetMin + 1];

    for (int i = 0; i <= numIndices.length - 1; i++) {
    numIndices[i] = -1;
    }
    for (int i = 0; i <= nums.length - 1; i++) {
    if (nums[i] >= targetMin && nums[i] <= targetMax) {
    int offset = -targetMin;
    if (numIndices[(target - nums[i]) + offset] != -1) {
    return new int[] { numIndices[(target - nums[i]) + offset], i };
    } else {
    numIndices[nums[i] + offset] = i;
    }
    }
    }
    return new int[] { 0, 0 };
    }
    }
    stevenbipt
        4
    stevenbipt  
    OP
       2018-04-05 23:07:52 +08:00
    完啦更鬼畜了= =妈耶
    lhx2008
        5
    lhx2008  
       2018-04-05 23:08:36 +08:00 via Android   ❤️ 1
    这个代码现在直接提交会更快吗,历史的不算数的
    stevenbipt
        6
    stevenbipt  
    OP
       2018-04-05 23:09:31 +08:00
    @lhx2008 不会,就是 3ms,上次看到最快的是用 hash 表完成的( 6ms)
    lcdtyph
        7
    lcdtyph  
       2018-04-05 23:09:56 +08:00   ❤️ 1
    这就是实现了一个哈希函数是 hash(x) -> x 的哈希表啊。
    而且这个代码在数据极差很大的时候肯定会 MLE
    stevenbipt
        8
    stevenbipt  
    OP
       2018-04-05 23:15:22 +08:00
    @lcdtyph 谢谢大佬指点(。・∀・)ノ゙
    stevenbipt
        9
    stevenbipt  
    OP
       2018-04-05 23:23:51 +08:00
    @lcdtyph 弱弱问大佬一句( mle 什么意思啊= =)
    lcdtyph
        10
    lcdtyph  
       2018-04-05 23:27:33 +08:00   ❤️ 2
    @stevenbipt #9 MLE 是 memory limit error 就是内存超限,TLE 就是时间超限
    stevenbipt
        11
    stevenbipt  
    OP
       2018-04-05 23:30:47 +08:00 via Android
    @lcdtyph 谢谢大佬指点😚😚😚
    lcdtyph
        12
    lcdtyph  
       2018-04-05 23:56:01 +08:00 via iPhone
    @stevenbipt 啊…是 memory limit exceeded 抱歉
    DeweyLiu
        13
    DeweyLiu  
       2018-04-06 00:56:57 +08:00 via Android
    @stevenbipt 哈希 好像 1ms 就搞定了
    vegito2002
        14
    vegito2002  
       2018-04-06 01:15:50 +08:00 via iPad
    自己拿数组造轮子做 stack 做 map 的解法, 就是用来耍 OJ 玩的, 大概了解一下就行了, 真正面试的时候不会碰到这么蛋疼的公司的。
    stevenbipt
        15
    stevenbipt  
    OP
       2018-04-06 08:07:43 +08:00
    @DeweyLiu 貌似在 java 上最快就 3ms
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5306 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 40ms · UTC 05:45 · PVG 13:45 · LAX 22:45 · JFK 01:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.