leetcode 第599题. 两个列表的最小索引总和,真心求优化

Question

public string[] FindRestaurant(string[] list1, string[] list2) {
Dictionary<string, int> dic = new Dictionary<string, int>(list1.Length);
for (int i = 0; i < list1.Length; i++)
{
dic.Add(list1[i], i);
}
List<string> result = new List<string>();
int min = -1;
for (int i = 0; i < list2.Length; i++)
{
if (dic.Keys.Contains(list2[i]))
{
int t = i + dic[list2[i]];
if (min == -1 || min == t)
{
min = t;
result.Add(list2[i]);
}
else if (t < min)
{
min = t;
result.Clear();
result.Add(list2[i]);
}
}
}
　　 return result.ToArray();
}

效果很不好:

执行用时 :504 ms, 在所有C#提交中击败了79.31%的用户
内存消耗 :39.9 MB, 在所有C#提交中击败了75.00%的用户

Answer 1

对你的代码修改如下，

public class Solution {
   
public string[] FindRestaurant(string[] list1, string[] list2) {
    

    Dictionary<string, int> dic = new Dictionary<string, int>(list1.Length);
    for (int i = 0; i < list1.Length; i++)
    {
        dic.Add(list1[i], i);
    }
    int[] result = new int[list2.Length];
    
    int[] num = new int[list2.Length];
    int min = 9999999;
    int pos=0;
    int pos2=0;
    int tag=0;
    for (int i = 0; i < list2.Length; i++)
    {
        if(i>min) break;
        if (dic.ContainsKey(list2[i]))
        {
            int t = i + dic[list2[i]];
            
            if(min >= t)
            {
                result[pos]=i;
                num[pos++]=t;
              
                if(min==t)
                    tag++;
                else{
                    tag=1;
                     min = t;
                }
                 
            }
        }
    }
    string[] ans = new string[tag];
    for(int i=0;i<pos;i++)
    {
        if(num[i]==min)
        {
           ans[pos2++]=list2[result[i]];
        }
    }
    
    　　 return ans;
}

}

去试一下，我觉得LeetCode的判题机，执行用时波动很大，如果你和最快的程序差距在几十ms以内，那么你就不用去优化时间效率了。