두 목록의 최소 인덱스 합계

난이도 쉽게
자주 묻는 질문 신탁 큰소리로 말하다
해시 해싱조회수 24

Ankur와 Rishabh는 두 친구이며 시장에서 과일을 사고 싶어합니다. 둘 다 좋아하는 과일 목록이 있습니다. 문자열. 당신의 임무는 최소 지수 합계로 그들이 가장 좋아하는 과일을 찾을 수 있도록 돕는 것입니다. 둘 사이의 선택에 동점이 있으면 주문 요구 사항없이 모두 출력합니다. 항상 답이있을 것이라고 가정 할 수 있습니다.

입력

[ "애플", "오렌지", "망고", "리치"]

[ "구아바", "딸기", "리치"]

산출

리치

설명

리치는 그들 사이의 유일한 일반적인 과일입니다.

입력

[ "오렌지", "망고", "리치", "사과", "딸기"]

[ "딸기", "오렌지", "사과"]

OUPUT

주황색

설명

둘 다 마음에 드는 것으로 지수 액이 가장 적은 과일은 "주황색" 지수 합계 포함 1 (0 + 1).

두 목록의 최소 인덱스 합계 알고리즘

  1. 두 목록을 입력 값으로 가져옵니다.
  2. 지도와 벡터를 선언합니다.
  3. 인덱스와 함께 list1의 값을 맵에 추가하십시오.
  4. list2를 탐색하고 list2의 요소가 맵에 있는지 확인하고 'minimum'을 정수의 최대 값으로 설정합니다.
  5. 찾은 경우 현재 인덱스와 찾은 요소 인덱스의 합계를 합계에 저장하고 합계에 저장합니다.
  6. 최소값이 참이면 합계보다 작은 지 확인한 다음 합계를 최소값에 저장합니다.
  7. 결과 벡터를 지우고 새 요소를 저장합니다.
  8. 합계가 최소값과 같으면 결과 벡터에 값을 더하기 만하면됩니다.
  9. 출력 벡터를 인쇄하면 답을 얻을 수 있습니다.

설명

우선, 우리는 commonThings1과 commonThings2의 두 가지 목록입니다. 이것이 우리의 입력 값입니다. 그래서 우리가하려고하는 것은 우리가 출력을 찾을 함수에이 목록을 전달하는 것입니다.

일부 문자열이 입력으로 list1 및 list2로 저장된 목록을 얻습니다. 해싱을 사용하고 HashMap을 컬렉션으로 사용할 것입니다. HashMap을 사용하여 요소를 Map 및 해당 인덱스에 저장할 수 있으며 인덱스는 최소 인덱스 합계를 찾는 데 도움이됩니다. 출력을 저장하고 나중에 출력 할 문자열 "출력"벡터를 선언 할 수 있습니다.

그래서 우리는 이것을 이해하기 위해 예를 취할 수 있습니다.

list1 : [ "애플", "오렌지", "망고", "리치"]

list2 : [ "구아바", "딸기", "리치"]

list1을 탐색하고 list1의 모든 값을 맵에 추가합니다. 그런 다음지도에 목록 요소 중 하나가 포함되어 있으면 list2 요소를 확인한 다음 항목을 찾았지만 최소 최소 인덱스를 검색합니다. 합계와 최소값을 선언 할 것이므로 우리가 찾은 list1 요소 인덱스와 list2 요소 인덱스의 합계는 최소값입니다. 최소값을 찾은 경우 결과 출력을 지우고 그 안에 새 항목을 만듭니다. 또한 두 요소의 최소 인덱스 합계가 같으면 이전 및 현재의 경우 새 요소를 푸시합니다.

예에서 우리는 이것을 취했습니다. 우리는 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

두 목록의 최소 인덱스 합계에 대한 복잡성 분석

시간 복잡성

O (l1+l2)어디로 l1 및 l2 길이는 list1list2.

공간 복잡성

O (l * x) 어디에 x 이다 결과 목록의 길이 결과를 저장하는 데 사용되며 l 이다 최대 문자열 길이.

참조

Translate »