两个列表的最小索引和


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

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,它的最小索引最小,并且所有它都是列表中唯一的元素。

两个列表的最小索引和

两个列表的最小索引和的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 是的长度 list1list2.

空间复杂度

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

參考資料