C++ प्रोग्राम: O(n) जटिलता के साथ दूसरा सबसे छोटा तत्व खोजना

यह C++ प्रोग्राम एक ऐरे में दूसरा सबसे छोटा (Second Smallest) तत्व O(n) समय जटिलता में खोजता है। यह सिंगल पास में दो वेरिएबल्स (सबसे छोटा और दूसरा सबसे छोटा) को मेंटेन करता है।

एल्गोरिदम

शुरुआत
  1. फंक्शन SecondSmallest():
     आर्गुमेंट्स: ऐरे पॉइंटर a, तत्वों की संख्या n
     बॉडी:
     - s1 (सबसे छोटा) और s2 (दूसरा सबसे छोटा) को INT_MAX से इनिशियलाइज़ करें
     - ऐरे को ट्रैवर्स करें:
         यदि वर्तमान तत्व < s1: s2 = s1, s1 = वर्तमान तत्व
         अन्यथा यदि वर्तमान तत्व s1 और s2 के बीच है: s2 = वर्तमान तत्व
     - यदि s2 == INT_MAX: "No second smallest element" प्रिंट करें
     - अन्यथा s2 प्रिंट करें
समाप्ति

उदाहरण कोड

#include <iostream>
#include <climits>
using namespace std;

void SecondSmallest(int *a, int n) {
    int s1 = INT_MAX, s2 = INT_MAX;
    
    for (int i = 0; i < n; i++) {
        if (a[i] < s1) {
            s2 = s1;
            s1 = a[i];
        } else if (a[i] > s1 && a[i] < s2) {
            s2 = a[i];
        }
    }
    
    if (s2 == INT_MAX)
        cout << "No second smallest element present";
    else
        cout << "Second smallest element is: " << s2;
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    
    int arr[n];
    for (int i = 0; i < n; i++) {
        cout << "Enter element " << i+1 << ": ";
        cin >> arr[i];
    }
    
    SecondSmallest(arr, n);
    return 0;
}

आउटपुट

Enter the number of elements: 5
Enter element 1: 1
Enter element 2: 2
Enter element 3: 1
Enter element 4: 3
Enter element 5: 4
Second smallest element is: 2

व्याख्या: ऐरे [1, 2, 1, 3, 4] में सबसे छोटा 1 है (दो बार), दूसरा सबसे छोटा यूनिक तत्व 2 है। प्रोग्राम डुप्लिकेट को सही ढंग से हैंडल करता है (a[i] > s1 चेक द्वारा)।

समय जटिलता: O(n) - सिंगल पास।

स्पेस जटिलता: O(1) - केवल दो वेरिएबल।

तुलना: सॉर्टिंग आधारित दृष्टिकोण O(n log n) लेता, यह अधिक कुशल है।