Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: O(n) समय और O(1) अतिरिक्त स्थान में डुप्लिकेट ज्ञात करना - सेट 1

मान लें हमारे पास 0 से n-1 तक की संख्याओं की एक सूची है। एक संख्या को जितनी बार संभव हो उतनी बार दोहराया जा सकता है। हमें बिना किसी अतिरिक्त स्थान के दोहराई जाने वाली संख्याएं ज्ञात करनी हैं। यदि n का मान 7 है, और सूची [5, 2, 3, 5, 1, 6, 2, 3, 4, 5] की तरह है। उत्तर 5, 2, 3 होगा।

इसे हल करने के लिए, हमें इन चरणों का पालन करना होगा:

सूची में प्रत्येक तत्व e के लिए, निम्न चरण करें:

  • sign := A[e का निरपेक्ष मान]
  • यदि sign धनात्मक है, तो इसे ऋणात्मक बनाएं
  • अन्यथा यह एक पुनरावृत्ति है।

उदाहरण

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

void findDuplicates(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        if (arr[abs(arr[i])] >= 0)
            arr[abs(arr[i])] *= -1;
        else
            cout << abs(arr[i]) << " ";
    }
}

int main() {
    int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    findDuplicates(arr, n);
}

आउटपुट

5 2 3 1
  1. - C++ STL में Set find() फ़ंक्शन

    C++ STL में Set find() फ़ंक्शन सेट कंटेनर में खोजे गए एलिमेंट के लिए एक इटरेटर लौटाता है। यदि एलिमेंट नहीं मिलता है तो इटरेटर सेट में अंतिम एलिमेंट के ठीक बाद की स्थिति की ओर इंगित करता है। एल्गोरिथम Begin    Define function printS() to print elements of set container.    initia

  1. Python में BST का माध्यिका O(n) समय और O(1) स्थान में ढूंढना Python में BST का माध्यिका O(n) समय और O(1) स्थान में ढूंढना

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) है, हमें उसका माध्यिका ढूंढना है। हम जानते हैं कि सम संख्या में नोड्स के लिए, माध्यिका = ((n/2वां नोड + (n+1)/2वां नोड) / 2। विषम संख्या में नोड्स के लिए, माध्यिका = (n+1)/2वां नोड। तो, यदि इनपुट इस तरह है तो आउटपुट 7 होगा। इसे हल करने के लिए, हम इन चरण

  1. - पायथन में O(n) समय और O(1) अतिरिक्त स्पेस में अधिकतम दोहराने वाली संख्या खोजें

    मान लीजिए हमारे पास आकार n का एक ऐरे है, यदि ऐरे में तत्व 0 से k-1 की रेंज में हैं। जहां k एक धनात्मक पूर्णांक है और k <= n। हमें इस ऐरे में अधिकतम दोहराने वाली संख्या ढूंढनी है।तो, यदि इनपुट k = 8 और A = [3, 4, 4, 6, 4, 5, 2, 8] जैसा है, तो आउटपुट 4 होगा।इसे हल करने के लिए, हम निम्नलिखित चरणों का प