दोन यादीतील किमान निर्देशांकांची बेरीज


अडचण पातळी सोपे
वारंवार विचारले ओरॅकल केकाटणे
हॅश हॅशिंग

अंकुर आणि habषभ हे दोन मित्र आहेत आणि त्यांना बाजारातून काही फळे खरेदी करायची आहेत. त्यांच्याकडे प्रतिनिधित्त्व केलेल्या त्यांच्या आवडत्या फळांची यादी आहे स्ट्रिंग्स. आपले कार्य म्हणजे त्यांना किमान अनुक्रमे बेरीजसह त्यांचे सामान्य आवडते फळ शोधण्यात मदत करणे. जर त्यांच्यामध्ये निवडीमध्ये टाय असेल तर ऑर्डरची आवश्यकता नसल्यास त्या सर्वांना आउटपुट करा. आपण असे समजू शकता की उत्तर नेहमीच अस्तित्त्वात असेल.

उदाहरण

इनपुट

[“Appleपल”, “केशरी”, “आंबा”, “लिची”]

[“पेरू”, “स्ट्रॉबेरी”, “लिची”]

उत्पादन

लिची

स्पष्टीकरण

लीची हे एकमेव सामान्य फळ आहे.

इनपुट

[“संत्रा”, “आंबा”, “लिची”, “Appleपल”, “स्ट्रॉबेरी”]

[“स्ट्रॉबेरी”, “ऑरेंज”, “Appleपल”]

औपुत

संत्रा

स्पष्टीकरण

फळ ज्याचे दोन्ही आवडीचे असतात आणि कमीतकमी अनुक्रमणिका बेरीज असते “केशरी” निर्देशांक बेरीजसह 1 (0 + 1)

दोन सूचीच्या किमान निर्देशांक बेरीजसाठी अल्गोरिदम

  1. आमची इनपुट मूल्ये म्हणून दोन याद्या मिळवा.
  2. नकाशा आणि वेक्टर घोषित करा.
  3. त्यांच्या अनुक्रमणिकांसह नकाशामध्ये सूची 1 ची मूल्ये जोडा.
  4. सूची 2 चा आढावा घ्या आणि नकाशामध्ये यादी 2 चे घटक अस्तित्त्वात आहेत का ते तपासा आणि पूर्णांकच्या अधिकतम मूल्यावर 'किमान' सेट करा.
  5. आढळल्यास वर्तमान निर्देशांकांची बेरीज संचयित करा आणि घटक निर्देशांकांची बेरीज आणि बेरीज संचयित करा.
  6. किमान बरोबर असल्यास कमी बेरीज असल्यास ते तपासा, नंतर बेरीज किमान करा.
  7. परिणामी वेक्टर साफ करा आणि नवीन घटक संग्रहित करा.
  8. जर बेरीज किमान समान असेल तर फक्त परिणामी वेक्टरमध्ये मूल्य जोडा.
  9. आउटपुट वेक्टर प्रिंट करा, आपल्याला आमचे उत्तर मिळेल.

स्पष्टीकरण

सर्व प्रथम, आम्ही कॉमन थिंग्ज 1 आणि कॉमनथिंग्ज 2 या दोन सूची आहेत. ही आमची इनपुट व्हॅल्यूज आहेत. तर आपण या सूची आपल्या कार्यामध्ये पार पाडणार आहोत ज्यामधे आपले आऊटपुट मिळेल.

आमच्याकडे त्या सूची आहेत ज्यात यामध्ये काही तार आपल्या इनपुट म्हणून list1 आणि list2 म्हणून संग्रहित आहेत. आम्ही आमचा संग्रह म्हणून हॅशिंग आणि हॅशमॅप वापरणार आहोत. हॅशमॅप वापरुन आपण घटक नकाशे व त्या अनुक्रमणिकेत संग्रहित करू शकतो, अनुक्रमणिका आपल्याला किमान अनुक्रमणिका बेरीज शोधण्यात मदत करतात. आपण स्ट्रिंग “आउटपुट” चे वेक्टर घोषित करू शकतो ज्यामधे आपण आपले आउटपुट संग्रहित करू आणि नंतर ते प्रिंट करू.

हे समजण्यासाठी आपण उदाहरण घेऊ शकतो.

list1: [“Appleपल”, “केशरी”, “आंबा”, “लीची”]

list2: [“पेरू”, “स्ट्रॉबेरी”, “लिची”]

आम्ही यादी 1 ओलांडू आणि सूची 1 ची सर्व मूल्ये नकाशात जोडू. नंतर आम्ही नकाशामध्ये यादीतील कोणत्याही घटकांचा समावेश असल्यास यादी 2 घटकांची तपासणी करू. मग आम्हाला ती वस्तू सापडली, परंतु आम्ही किमान किमान अनुक्रमणिका शोधू, त्यासाठी आम्ही बेरीज आणि किमान घोषित करीत आहोत, आम्ही तपासणी करीत आहोत list1 घटक अनुक्रमणिका आणि list2 घटक निर्देशांक आम्हाला आढळला, त्यापैकी बेरीज किमान आहेत, जर आपल्याला किमान सापडले तर आम्ही परिणामी आउटपुट साफ करतो आणि त्यामध्ये नवीन प्रविष्टी बनवितो आणि तसेच दोन घटक किमान निर्देशांक समान असल्यास मागील, आणि चालू, तर आपण फक्त नवीन घटक ढकलू.

उदाहरणार्थ, आम्ही यात घेतले आहे. आमच्याकडे फक्त लिची असल्याचे आढळले आहे आणि कमीतकमी किमान अनुक्रमणिका आहे आणि त्या सर्वांमध्ये याद्यांमध्ये आढळणारा एकमेव घटक आहे.

दोन यादीतील किमान निर्देशांकांची बेरीज

दोन सूचीच्या किमान निर्देशांक बेरीजसाठी सी ++ प्रोग्राम

#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

दोन सूचीच्या किमान निर्देशांक बेरीजसाठी जावा प्रोग्राम

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 लांबी आहेत यादी 1 आणि यादी 2.

स्पेस कॉम्प्लेक्सिटी

ओ (एल * एक्स) जेथे x आहे परिणामी यादीची लांबी परिणाम संचयित करण्यासाठी वापरले आणि l आहे जास्तीत जास्त स्ट्रिंग लांबी.

संदर्भ