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

LeetCode 第一题: 两数之和

  •  
  •   shunfy · 2021-03-24 17:56:22 +08:00 · 2296 次点击
    这是一个创建于 1100 天前的主题,其中的信息可能已经有所发展或是发生改变。

    LeetCode 第一题: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。

    #include <map>
    using namespace std;
    
    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            map<int, int> tmpMap;
            int tmpNumber;
            for(int i=0, imax = nums.size(); i<imax; ++i)
            {
                tmpNumber = nums[i];
                if(tmpMap.find(tmpNumber) != tmpMap.end())
                    return { tmpMap[tmpNumber], i };
                else
                    tmpMap[target - tmpNumber] = i;
            }
            return {};
        }
    };
    

    以上是 Java 代码,LeetCode 执行时间是 4ms.

    class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> tmpMap = new HashMap<>();
            int tmpNumber;
            for(int i=0, imax = nums.length; i<imax; i++)
            {
                tmpNumber = nums[i];
                if(tmpMap.containsKey(tmpNumber))
                    return new int[]{tmpMap.get(nums[i]), i};
                tmpMap.put(target - nums[i], i); 
            }
            return null;
        }
    }
    

    以上是 Java 代码,LeetCode 执行时间是 0ms.

    using System.Collections.Generic;
    
    public class Solution
    {
        public int[] TwoSum(int[] nums, int target)
        {
            Dictionary<int, int> tmpTab = new Dictionary<int, int>(1);
            int tmpNumber;
            for (int i = 0, imax = nums.Length; i < imax; ++i)
            {
                tmpNumber = nums[i];
                if (tmpTab.ContainsKey(tmpNumber))
                    return new int[] { tmpTab[tmpNumber], i };
                else
                    tmpTab[target - tmpNumber] = i;
            }
    
            return null;
        }
    }
    

    以上是 CS 代码,执行时间竟然有 300ms


    为什么执行时间会相差这么大呢? 是因为 LeetCode 的执行环境问题吗? 此逻辑还有优化的空间吗?

    7 条回复    2021-03-25 12:15:13 +08:00
    lewis89
        1
    lewis89  
       2021-03-24 18:01:13 +08:00
    leetcode 代码执行时间 你就当个笑话看就是了
    Jirajine
        2
    Jirajine  
       2021-03-24 18:03:38 +08:00 via Android
    你要比较,也得给足够大的数据集,多次运行,取平均时间,以排除冷启动、缓存等因素造成的干扰。
    shunfy
        3
    shunfy  
    OP
       2021-03-24 18:09:59 +08:00
    @lewis89 你说的可能是对的
    ch2
        4
    ch2  
       2021-03-24 18:15:13 +08:00   ❤️ 6
    刘翔和博尔特比赛跑 1 米,我哨子吹完开始计时,博尔特愣了一下,成绩慢了 300ms
    shpkng
        5
    shpkng  
       2021-03-24 22:44:31 +08:00
    LeetCode 同一段代码的执行速度都能差一半的
    Chenamy2017
        6
    Chenamy2017  
       2021-03-25 09:07:13 +08:00
    多跑几次,取平均值看看
    obtain
        7
    obtain  
       2021-03-25 12:15:13 +08:00
    比较时间执行的快慢没意义的,要比较写的算法时间复杂度。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3348 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 13:23 · PVG 21:23 · LAX 06:23 · JFK 09:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.