एक ऐरे में सकारात्मक नकारात्मक मूल्यों की जोड़ी


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना बेलजब्बर हनीवेल Hulu Nvidia रॉबिन हुड भौंकना
ऐरे हैश

सकारात्मक नकारात्मक मानों की जोड़ी में सरणी समस्या हमने अलग-अलग पूर्णांक का एक ए दिया है, सरणी में मौजूद संख्या के सकारात्मक मूल्य और ऋणात्मक मान वाले सभी जोड़ों को प्रिंट करें। हमें उनकी घटनाओं के क्रम में जोड़े छापने की जरूरत है। एक जोड़ी जिसका कोई भी तत्व पहले दिखाई देता है, उसे पहले मुद्रित किया जाना चाहिए।

उदाहरण

इनपुट:

A[]={2, 3, -1, -2, 9, 1}

आउटपुट:

Pairs having positive value and negative in the array are: -2 2 -1 1

दृष्टिकोण 1: क्रूर बल

इनपुट एरे में प्रत्येक तत्व A [i] के लिए, अगर -A [i] एरे में मौजूद सूचकांक के साथ अधिक से अधिक होता है, अगर मैं मौजूद हूं तो इस जोड़ी को प्रिंट करता है।

कलन विधि

  1. I को 0 से n-1 तक के लिए एक लूप चलाएं
    1. J के लिए एक लूप चलाएं i + 1 से n-1
      1. यदि A [i] -A [j] के बराबर है, तो इस जोड़ी को प्रिंट करें।
    2. वापसी।

एक सरणी में सकारात्मक नकारात्मक मूल्यों की जोड़ी खोजने के लिए सी ++ कार्यक्रम

#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
    int n = A.size();
    cout << "Pairs having positive value and negative in the array are: ";
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (A[i] == -A[j])
            {
                if (A[i] <= 0)
                {
                    cout << A[i] << " " << (-A[i]) << " ";
                }
                else
                {
                    cout << (-A[i]) << " " << A[i] << " ";
                }
            }
        }
    }
    cout << endl;
    return;
}
int main()
{
    vector<int> A = {2, 3, -1, -2, 9, 1};
    printPairs(A);
    return 0;
}
Pairs having positive value and negative in the array are: -2 2 -1 1

एक सरणी में सकारात्मक नकारात्मक मूल्यों की जोड़ी खोजने के लिए जावा कार्यक्रम

public class Main
{
    static void printPairs(int[] A)
    {
        int n = A.length;
        System.out.print("Pairs having positive value and negative in the array are: ");
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (A[i] == -A[j])
                {
                    if (A[i] <= 0)
                    {
                       A[i]=-A[i];
                    }
                    System.out.print(A[i]+" -"+A[i]+" ");
                }
            }
        }
        return;
    }
  public static void main(String[] args) {
    int[] A={2, 3, -1, -2, 9, 1};
    printPairs(A);
  }
}
Pairs having positive value and negative in the array are: 2 -2 1 -1

जटिलता विश्लेषण

समय की जटिलता

हम दो नेस्टेड छोरों का उपयोग कर रहे हैं, दोनों आकार एन। तो कुल समय जटिलता है ओ (एन ^ 2)

अंतरिक्ष की जटिलता

हम किसी भी अतिरिक्त स्थान का उपयोग नहीं कर रहे हैं इसलिए अंतरिक्ष जटिलता है ओ (1)

दृष्टिकोण 2: हैशिंग का उपयोग करना

मुख्य विचार

हम हैश तालिका में सरणी में कौन से तत्व मौजूद हैं, इसे स्टोर कर सकते हैं। अब सरणी में प्रत्येक तत्व A [i] के लिए, देखें कि hash तालिका में if -A [i] का मान 1 है या नहीं, यदि यह 1 है तो इस जोड़ी को और A [i] और decrement के मूल्य को प्रिंट करें [i] हैश तालिका में १ से ताकि हम एक ही जोड़ी को दो बार प्रिंट नहीं करेंगे।

कलन विधि

  1. एक हैश तालिका प्रारंभ करें।
  2. हैश तालिका में प्रत्येक तत्व की आवृत्ति को संग्रहीत करें।
  3. I को 0 से n-1 तक के लिए एक लूप चलाएं
    1. यदि हैश तालिका में –A [i] का मान 1 है, तो इस जोड़ी को प्रिंट करें और A [i] और –A [i] के मूल्य को 1 से घटाएं।

उदाहरण के साथ समझें

आइए इनपुट सरणी A [] = {2, 3, -1, -2, 9, 1} लें

तो हमारी हैश तालिका हम इस तरह दिखते हैं:

एक ऐरे में सकारात्मक नकारात्मक मूल्यों की जोड़ी

अब हम सरणी को पुन: व्यवस्थित करेंगे,

नारंगी रंग वर्तमान सूचकांक को दर्शाता है,

एक ऐरे में सकारात्मक नकारात्मक मूल्यों की जोड़ी एक ऐरे में सकारात्मक नकारात्मक मूल्यों की जोड़ी

एक ऐरे में सकारात्मक नकारात्मक मूल्यों की जोड़ी

तो अंतिम आउटपुट है: -2 -2 -1 1

एक सरणी में सकारात्मक नकारात्मक मूल्यों की जोड़ी खोजने के लिए सी ++ कार्यक्रम

#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
    int n = A.size();
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    cout << "Pairs having positive value and negative in the array are: ";
    for (int i = 0; i < n; i++)
    {
        if (hash_table[-A[i]] == 1)
        {
            if (A[i] <= 0)
            {
                cout << A[i] << " " << (-A[i]) << " ";
            }
            else
            {
                cout << (-A[i]) << " " << A[i] << " ";
            }
            hash_table[A[i]]--;
            hash_table[-A[i]]--;
        }
    }
    cout << endl;
    return;
}
int main()
{
    vector<int> A = {2, 3, -1, -2, 9, 1};
    printPairs(A);
    return 0;
}
Pairs having positive value and negative in the array are: -2 2 -1 1

एक सरणी में सकारात्मक नकारात्मक मूल्यों की जोड़ी खोजने के लिए जावा कार्यक्रम

import java.util.*; 
public class Main
{
    static void printPairs(int[] A)
    {
        int n = A.length;
        HashMap<Integer,Integer> hash_table = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            hash_table.put(A[i],1);
        }
        System.out.print("Pairs having positive value and negative in the array are: ");
        for (int i = 0; i < n; i++)
        {
            if(hash_table.containsKey(-1*A[i]) && hash_table.get(-1*A[i])==1)
            {
                if (A[i] <= 0)
                {
                    A[i]*=-1;
                }
                System.out.print(A[i]+" -"+A[i]+" ");
                hash_table.put(A[i],0);
                hash_table.put(-1*A[i],0);
            }
        }
        return;
    }
  public static void main(String[] args) {
    int[] A={2, 3, -1, -2, 9, 1};
    printPairs(A);
  }
}
Pairs having positive value and negative in the array are: -2 2 -1 1

जटिलता विश्लेषण

समय की जटिलता

हम दो बार पूरे सरणी को पुनरावृत्त कर रहे हैं, इसलिए समय जटिलता है पर).

अंतरिक्ष की जटिलता

हम एक हैश तालिका का उपयोग कर रहे हैं, इसलिए अंतरिक्ष जटिलता है पर).

संदर्भ