leetcode的每日一题更新(Minimum Index Sum of Two Lists)

题目:两个人,每个人有喜欢的餐厅字符串数组,找出他们共同爱好的餐厅并且要求index之和最小。返回一个字符串数组,因为可能有多个结果。
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".
解题思路:我只能用穷举法,因为做到一半看到它的排序顺序是根据第二个人的,所以将第二个数组作为外围,加入到要返回的数组中,后面遇到一个问题,因为是new的两个中最长的数组,所以出来的结果有null值,只能根据一个控制result数组的index来创建一个新的数组,将这个新数组返回,我这个解法太麻烦了,而且复杂度n2。附上代码:

public String[] findRestaurant(String[] list1, String[] list2) {
        if(list1==null || list2==null || list1.length==0 || list2.length==0 )return null;
        String[] result=null;
        int listindex=0;
        int min=2001;
        int resultindex=0;
        for(int i=0;i<list2.length;i++){
            for(int j=0;j<list1.length;j++){
                if(list1[j].equals(list2[i])){
                    if( min > i+j){
                        listindex=i;
                        min=i+j;
                        result=new String[list1.length>list2.length?list1.length:list2.length];
                        resultindex=0;
                        result[resultindex++]=list1[j];
                    }else if(min == i+j){
                        result[resultindex++]=list1[j];
                    }
                }
            }
        }
        if(min==2001)return null;
        String[] realresult=new String[resultindex];
        for(int k=0;k<resultindex;k++){
            realresult[k]=result[k];
        }
        return realresult;    
    }

看了以下其他人的解法,他们是用hashmap来减少一重循环,直接键值匹配,我不会算精确的复杂度,不过用类库的方法肯定比我的n2的复杂度好一些,代码就不复制了。看看就行。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容