İki Siyahının Minimum İndeks Cəmi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Kahin Vəngilti
Sükut HashingBaxılıb 25

Ankur və Rishabh iki dostdur və bazardan meyvə almaq istəyirlər. Hər ikisində də təmsil etdikləri ən sevdikləri meyvələrin siyahısı var strings. Tapşırığınız, minimum indeks cəmi ilə ən çox sevdikləri meyvələri tapmalarına kömək etməkdir. Aralarındakı seçimdə bərabərlik varsa, hamısını sifariş tələb etmədən çıxarın. Hər zaman bir cavabın olacağını düşünə bilərsiniz.

misal

Input

[“Alma”, “Portağal”, “Mango”, “Lichi”]

[“Guava”, “Çiyələk”, “Lichi”]

Buraxılış

Lichi

Izahat

Lichi, aralarındakı yeganə ümumi meyvədir.

Input

[“Portağal”, “Mango”, “Lichi”, “Alma”, “Çiyələk”]

[“Çiyələk”, “Portağal”, “Alma”]

Çıxış

Narıncı

Izahat

Hər ikisinin də ən sevdiyi və ən az indeks cəminə sahib olan meyvədir “Narıncı” indeks cəmi ilə 1 (0 + 1).

İki Siyahının Minimum İndeks Cəmi Alqoritmi

  1. Giriş siyahımız kimi iki siyahını alın.
  2. Xəritə və bir vektor elan edin.
  3. List1 dəyərlərini indeksləri ilə xəritəyə əlavə edin.
  4. List2-yə keçin və list2 elementinin xəritədə olub olmadığını yoxlayın və 'minimum' ədədi maksimum dəyərinə qoyun.
  5. Əgər tapılsa, cari indeksin cəmini və tapılan element indeksini cəminə, mağazanı cəminə yazın.
  6. Minimumun doğru olduqda cəmdən az olub olmadığını yoxlayın, cəmi minimuma yığın.
  7. Nəticə vektorunu silin və yeni elementi saxlayın.
  8. Cəmi minimuma bərabərdirsə, nəticəni alınan vektora sadəcə dəyər əlavə edin.
  9. Çıxış vektorunu çap edin, cavabımızı alacağıq.

Izahat

Hər şeydən əvvəl, biz commonThings1 və commonThings2 kimi iki siyahıyıq. Bunlar bizim giriş dəyərlərimizdir. Beləliklə, nə edəcəyiksə, bu siyahıları öz nəticəmizi tapacağımız funksiyamıza keçirəcəyik.

Bəzi sətirlərin daxilində list1 və list2 olaraq saxlandığı siyahıları əldə edirik. HashMap və HashMap'ı kolleksiyamız olaraq istifadə edəcəyik. HashMap istifadə edərək elementləri Map və indekslərində saxlaya bilərik, indekslər ən az indeks cəmini tapmaqda bizə kömək edir. Çıxışımızı saxlayacağımız və daha sonra çap edəcəyimiz "çıxış" simli bir vektor elan edə bilərik.

Bunu anlamaq üçün bir nümunə götürə bilərik.

list1: [“Alma”, “Portağal”, “Mango”, “Lichi”]

list2: [“Guava”, “Çiyələk”, “Lichi”]

List1-i keçib xəritəyə list1-in bütün dəyərini əlavə edəcəyik. Sonra list2 elementlərini yoxlayacağıq ki, xəritədə siyahı elementlərindən biri varsa, onda maddəni tapdıq, lakin minimum minimum indeksi axtaracağıq, bunun üçün cəmi və minimumu elan edəcəyik, yoxlayacağıq list1 element indeksi və list2 element indeksini tapdıq, bunların cəmi hamısı minimumdur, minimum tapsaq, nəticəni çıxarıb yeni bir giriş edirik və eyni zamanda iki element ən kiçik indeks cəmi bərabərdirsə, əvvəlki və cari, onda yalnız yeni elementi itələyəcəyik.

Nümunədə, götürmüşük. yalnız Lichi olan və ən az minimum indeksin uyğunluğu var və bunların hamısında siyahılardakı yeganə element var.

İki Siyahının Minimum İndeks CəmiPin

İki Siyahının Minimum İndeks Cəmi üçün C ++ Proqramı

#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

İki Siyahının Minimum İndeks Cəmi üçün Java Proqramı

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

İki Siyahının Minimum İndeks Cəmi üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (l1+l2), Harada l1 və l2 uzunluqlarıdır siyahısı1siyahısı2.

Kosmik Mürəkkəblik

O (l * x) hara x dır,-dir,-dur,-dür nəticələnən siyahının uzunluğu nəticəni saxlamaq üçün istifadə olunur və l dır,-dir,-dur,-dür maksimum simli uzunluq.

References

Translate »