两个列表的最小索引和  


难度级别 易得奖学金
经常问 神谕 狗吠声
哈希 哈希

Ankur和Rishabh是两个朋友,想从市场上购买一些水果。 他们都有自己喜欢的水果的清单,以 字符串。 您的任务是帮助他们以最小的索引总和找到他们最喜欢的水果。 如果它们之间的选择有关系,则将其全部输出而无需订购。 您可以假设将始终存在答案。

使用案列  

输入

[“ Apple”,“ Orange”,“ Mango”,“ Lichi”]

[“番石榴”,“草莓”,“荔枝”]

输出

荔枝

说明

荔枝是它们之间唯一的共同果实。

输入

[“橙色”,“芒果”,“荔枝”,“苹果”,“草莓”]

[“草莓”,“橙色”,“苹果”]

输出中

橘色

说明

两者最喜欢且索引总和最小的水果是 “橙子” 有指数总和 1 (0 + 1)。

两个列表的最小索引和的算法  

  1. 获取两个列表作为我们的输入值。
  2. 声明地图和向量。
  3. 将list1的值及其索引添加到映射中。
  4. 遍历list2并检查列表中是否存在list2的元素,并将'minimum'设置为整数的最大值。
  5. 如果找到,则将当前索引的和存储,并将找到的元素索引存储到sum中,然后存储到sum中。
  6. 检查最小值是否小于总和(如果为true),然后将总和存储为最小值。
  7. 清除结果向量并存储新元素。
  8. 如果总和等于最小值,则只需将值添加到结果向量中即可。
  9. 打印输出向量,我们将得到答案。
参见
数组中不同的相邻元素

说明  

首先,我们有两个列表,分别是commonThings1和commonThings2。 这些是我们的输入值。 因此,我们要做的是将这些列表传递到我们要在其中查找输出的函数中。

我们得到其中存储了一些字符串的那些列表作为list1和list2作为我们的输入。 我们将使用哈希并将HashMap用作集合。 使用HashMap,我们可以将元素存储到Map及其索引中,索引帮助我们找出最小的索引和。 我们可以声明一个字符串“ output”的向量,在其中我们将存储我们的输出,然后打印出来。

因此,我们可以举一个例子来理解这一点。

list1:[“ Apple”,“ Orange”,“ Mango”,“ Lichi”]

清单2:[“番石榴”,“草莓”,“荔枝”]

我们将遍历list1并将list1的所有值添加到地图中。 然后,如果地图包含列表元素中的任何一个,我们将检查list2元素,然后找到该项目,但是我们将搜索最小最小值索引,为此我们将声明总和和最小值,我们将检查我们发现list1元素索引和list2元素索引,它们的总和是所有元素中的最小值,如果发现最小值,则清除结果输出并在其中添加新条目,并且如果两个元素的最小索引和相等,previous和当前,那么我们将只推新元素。

参见
最大产品子阵列

在示例中,我们已经采用了这种方式。 我们只有匹配项被发现是Lichi,它的最小索引最小,并且所有它都是列表中唯一的元素。

两个列表的最小索引和Pin

两个列表的最小索引和的C ++程序  

#include<bits/stdc++.h>
#include<unordered_map>
#include<vector>

using namespace std;

void getCommonString(vector<string> list1, vector<string> list2)
{
    unordered_map<string, int> map;
    for (int index = 0; index < list1.size(); index++)
        map[list1[index]] = index;

    vector<string> output;

    int minimum = INT_MAX;
    for (int j = 0; j < list2.size(); j++)
    {
        if (map.count(list2[j]))
        {
            int sum = j + map[list2[j]];
            if (sum < minimum)
            {
                minimum = sum;
                output.clear();
                output.push_back(list2[j]);
            }
            else if (sum == minimum)
                output.push_back(list2[j]);
        }
    }
    for (int i = 0; i < output.size(); i++)
        cout << output[i] << " ";
}
int main()
{
    vector<string> commonThings1;
    commonThings1.push_back("Apple");
    commonThings1.push_back("Orange");
    commonThings1.push_back("Mango");
    commonThings1.push_back("lichi");

    vector<string> commonThings2;
    commonThings2.push_back("Guava");
    commonThings2.push_back("Strawberry");
    commonThings2.push_back("lichi");

    getCommonString(commonThings1, commonThings2);
    return 0;
}
lichi

两个列表的最小索引和的Java程序  

import java.util.HashMap;
import java.util.Vector;

class commonThings
{
    public static void getCommonString(Vector<String> list1, Vector<String> list2)
    {
        Vector<String> output = new Vector<String>();
        HashMap<String, Integer> map = new HashMap<>();

        for (int index = 0; index < list1.size(); index++)
            map.put(list1.get(index), index);


        int minimum = Integer.MAX_VALUE;
        for (int j = 0; j < list2.size(); j++)
        {
            if (map.containsKey(list2.get(j)))
            {
                int sum = j + map.get(list2.get(j));
                if (sum < minimum)
                {
                    minimum = sum;
                    output.clear();
                    output.add(list2.get(j));
                }
                else if (sum == minimum)
                    output.add(list2.get(j));
            }
        }
        for (int i = 0; i < output.size(); i++)
            System.out.println(output.get(i) + " ");
    }
    public static void main(String[] args)
    {
        Vector<String> commonThings1 = new Vector<String>();
        commonThings1.add("apple");
        commonThings1.add("mango");
        commonThings1.add("banana");
        commonThings1.add("lichi");

        Vector<String> commonThings2 = new Vector<String>();
        commonThings2.add("guava");
        commonThings2.add("strawberry");
        commonThings2.add("lichi");

        getCommonString(commonThings1, commonThings2);
    }
}
lichi

两个列表的最小索引和的复杂度分析  

时间复杂度

1+l2),其中 l1 以及 l2 是的长度 list1 以及 list2.

空间复杂度

O(l * x) 哪里 x结果列表的长度 用于存储结果和 l最大字符串长度.

参见
查找不能表示为给定数组的任何子集之和的最小正整数值

參考資料