തന്നിരിക്കുന്ന മൂല്യത്തിന് തുല്യമായ നാല് ഘടകങ്ങൾ കണ്ടെത്തുക (ഹാഷ്‌മാപ്പ്)


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഗൂഗിൾ മൈക്രോസോഫ്റ്റ്
അറേ ഹാഷ് ക്രമപ്പെടുത്തൽ

“തന്നിരിക്കുന്ന മൂല്യത്തിന് (ഹാഷ്‌മാപ്പ്) സംഗ്രഹിക്കുന്ന നാല് ഘടകങ്ങൾ കണ്ടെത്തുക” എന്ന പ്രശ്‌നം പറയുന്നു, നിങ്ങൾക്ക് ഒരു സംഖ്യ അറേയും സം എന്ന സംഖ്യയുമുണ്ട്. തന്നിരിക്കുന്ന മൂല്യമായ “സം” ന് തുല്യമായ നാല് ഘടകങ്ങൾ അറേയിൽ ഉണ്ടോ എന്ന് നിർണ്ണയിക്കാൻ പ്രശ്ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു. ശരിയാണെങ്കിൽ, ഫംഗ്ഷൻ p ട്ട്‌പുട്ടുകൾ “അതെ”, അല്ലാത്തപക്ഷം “ഇല്ല”.

ഉദാഹരണം

തന്നിരിക്കുന്ന മൂല്യത്തിന് തുല്യമായ നാല് ഘടകങ്ങൾ കണ്ടെത്തുക (ഹാഷ്‌മാപ്പ്)

arr[] = {2, 7, 3, 2, 9, 5, 9, 3}
sum=25
Yes
arr[] = {4, 3, 1, 6, 8, 5, 4, 1}
sum=30
No

അൽഗോരിതം

  1. ലൂപ്പിലൂടെ സഞ്ചരിക്കുക, ഞാൻ <n - 1 ആയിരിക്കുമ്പോൾ.
    1. ലൂപ്പിലൂടെ സഞ്ചരിക്കുക, j = i + 1 <n
      1. Ar [i] + arr [j] ന്റെ മൂല്യം വാളിലേക്ക് സംഭരിച്ച് ഹാഷ് പട്ടികയിൽ സം-വാൽ ഉണ്ടോയെന്ന് പരിശോധിക്കുക.
        1. ശരിയാണെങ്കിൽ, താക്കോൽ നേടി നമ്പർ കണ്ടെത്തി ശരിയിലേക്ക് മടങ്ങുക.
      2. അല്ലെങ്കിൽ, i, j എന്നിവ ഹാഷ് ടേബിളിൽ കീയ്‌ക്കൊപ്പം arr [i] + arr [j] എന്ന് ഇടുക.
  2. തെറ്റായി മടങ്ങുക.

വിശദീകരണം

തന്നിരിക്കുന്ന മൂല്യം സംഗ്രഹിക്കുന്ന അറേയിൽ നാല് ഘടകങ്ങൾ നിലവിലുണ്ടോ എന്ന് നിർണ്ണയിക്കാൻ ആവശ്യപ്പെടുന്ന ഒരു പ്രശ്ന പ്രസ്താവന ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്നു. അതെ എങ്കിൽ പിന്തുടരുക, തുടർന്ന് ഫംഗ്ഷൻ അതെ എന്ന് പ്രിന്റുചെയ്യണം, അല്ലെങ്കിൽ ഇല്ല എന്ന് പ്രിന്റുചെയ്യുക. ഞങ്ങൾ ഉപയോഗിക്കാൻ പോകുന്നു ഹാഷിംഗ് ഈ പ്രശ്നം പരിഹരിക്കാൻ. അതുകാരണം, സാധ്യമായ ഉപ-അറേകളായി ജോടിയാക്കുന്ന കീയെ ഞങ്ങളുടെ ഘടകമായി സംഭരിക്കാനും അതിന്റെ സൂചികകളായി മൂല്യം സംഭരിക്കാനും കഴിയും, അതുവഴി നമുക്ക് അത് പരിശോധിക്കാൻ കഴിയും.

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം:

ഉദാഹരണം

arr [] = {2, 7, 3, 2, 9, 5, 9, 3}, തുക = 25

ഇവിടെ ഞങ്ങൾ ഒരു ഉദാഹരണം എടുത്തു. ഞങ്ങൾ ഒരു പ്രഖ്യാപിച്ചു ബൂളിയൻ ശരി, തെറ്റ് എന്നിവയിലേക്ക് മടങ്ങാൻ പോകുന്ന പ്രവർത്തനം. ഞങ്ങളുടെ ആർഗ്യുമെന്റുകളിലൊന്ന് ഏതെങ്കിലും ലിസ്റ്റ് അല്ലെങ്കിൽ വെക്റ്റർ ആയതിനാൽ, ഞങ്ങളുടെ മാപ്പിൽ, ഏത് വസ്തുക്കളുടെ ഉപയോഗമാണ് ഞങ്ങൾ ഉപയോഗിക്കാൻ പോകുന്നത്. അതിനാൽ അടിസ്ഥാനപരമായി നമ്മൾ അറേകളിലൂടെ സഞ്ചരിക്കാൻ പോകുന്നു, എന്നാൽ ഒരു അറേയുടെ ഓരോ ഘടകങ്ങളും ഒരു സമയത്ത് ഒരു ബാഹ്യ ലൂപ്പിൽ എടുത്ത് ഒരു സൂചിക മുന്നോട്ട് വരുന്ന ബാക്കി മൂലകങ്ങളെ രണ്ടാമത്തെ ആന്തരിക ലൂപ്പിലൂടെ സഞ്ചരിക്കുന്നു.

Ar [i] + arr [j] ആയ രണ്ട് മൂലകങ്ങളുടെയും ആകെത്തുക ഞങ്ങൾ എടുത്ത് val എന്ന് വിളിക്കുന്ന ചില വേരിയബിളിലേക്ക് സംഭരിക്കുകയും തുടർന്ന് സം-വാൽ ഉണ്ടോ എന്ന് പരിശോധിക്കുകയും ചെയ്യുന്നു ഹാഷ്‌ടേബിൾ അല്ലെങ്കിൽ ഇല്ലെങ്കിൽ, മൂലകങ്ങളെ മാപ്പിലേക്ക് തള്ളുക, നമുക്ക് അറേയുടെ മൂലകം 2 ഉം 7 ഉം ഉണ്ടെന്ന് കരുതുക (arr [i], arr [j]) ആകെ തുക 9 ഉം സം-മൂല്യം 25-9 18 ഉം ആണ് ഹാഷ് പട്ടികയിൽ‌ ഇല്ല, അതിനാൽ‌ ഞങ്ങൾ‌ 9 ഉം നിലവിലെ സൂചികകളും 0 ഉം 1 ഉം ആണ്‌, അതിനാൽ‌ സം-ആർ‌ [i] + arr [j] പട്ടികയിലുണ്ടോ ഇല്ലയോ എന്ന് പിന്നീട് കണ്ടെത്താനാകും. നിലവിലുണ്ടെങ്കിൽ, കീയുടെ മൂല്യങ്ങൾ നേടുകയും അതിൽ ചില നിബന്ധനകൾ പരിശോധിക്കുകയും ചെയ്യുക, അത് തൃപ്തികരമാണെങ്കിൽ ശരിയിലേക്ക് മടങ്ങുക. അതിനർത്ഥം ഞങ്ങളുടെ ഉത്തരം കണ്ടെത്തി എന്നാണ്.

തന്നിരിക്കുന്ന മൂല്യത്തിന്റെ ആകെത്തുകയുള്ള നാല് ഘടകങ്ങൾ കണ്ടെത്താനുള്ള സി ++ കോഡ് (ഹാഷ്‌മാപ്പ്)

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

typedef pair<int, int> Pair;

bool getFourNumber(int arr[], int n, int sum)
{
    unordered_map<int, vector<Pair>> map;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int val = sum - (arr[i] + arr[j]);
            if (map.find(val) != map.end())
            {
                for (auto pair : map.find(val)->second)
                {
                    int x = pair.first;
                    int y = pair.second;
                    if ((x != i && x != j) && (y != i && y != j))
                    {
                        return true;
                    }
                }
            }
            map[arr[i] + arr[j]].push_back({i, j});
        }
    }
    return false;
}
int main()
{
    int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
    int sum = 25;
    int n = sizeof(arr) / sizeof(arr[0]);
    if(getFourNumber(arr, n, sum))
        cout << "Yes";
    else
        cout<<"No";
    return 0;
}
Yes

തന്നിരിക്കുന്ന മൂല്യത്തിന്റെ ആകെത്തുകയുള്ള നാല് ഘടകങ്ങൾ കണ്ടെത്താനുള്ള ജാവ കോഡ് (ഹാഷ്‌മാപ്പ്)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Pair
{
    public int x, y;
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
class printQuadruplets
{
    public static boolean getFourNumber(int[] arr, int n, int sum)
    {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int val= (arr[i] + arr[j]);
                if (map.containsKey(sum-val))
                {
                    for (Pair pair : map.get(sum-val))
                    {
                        int x = pair.x;
                        int y = pair.y;
                        if ((x != i && x != j) && (y != i && y != j))
                        {
                            return true;
                        }
                    }
                }
                map.putIfAbsent(arr[i] + arr[j], new ArrayList<>());
                map.get(arr[i] + arr[j]).add(new Pair(i, j));
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
        int sum = 25;
        if (getFourNumber(arr, arr.length, sum))
        {
            System.out.println("Yes");
        }
        else
            System.out.println("No");
    }
}
Yes

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n2എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഈ സമയം സങ്കീർണ്ണത കൈവരിക്കാൻ ഹാഷ്‌മാപ്പ് ഉപയോഗിക്കുന്നത് ഞങ്ങളെ അനുവദിച്ചില്ലെങ്കിൽ അത് സാധ്യമാകുമായിരുന്നില്ല.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n2എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഏറ്റവും മോശം അവസ്ഥയിൽ മാപ്പിൽ സംഭരിക്കേണ്ട N ^ 2 ജോഡികൾ ഉണ്ടാകാം. അങ്ങനെ ബഹിരാകാശ സങ്കീർണ്ണത പോളിനോമിയലാണ്.