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

C++ में O(1) अतिरिक्त स्थान का उपयोग करके सरणी को पुनर्व्यवस्थित करें ताकि arr[i] arr[arr[i]] बन जाए

हमें एक धनात्मक पूर्णांक प्रकार की सरणी दी गई है, मान लीजिए arr[] किसी भी दिए गए आकार की, जिसमें सरणी के तत्वों का मान 0 से अधिक लेकिन सरणी के आकार से कम होना चाहिए। कार्य सरणी को इस तरह पुनर्व्यवस्थित करना है कि arr[i] दिए गए O(1) स्थान में arr[arr[i]] बन जाए और अंतिम परिणाम प्रिंट करें।

विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:

इनपुट: int arr[] = {0, 3, 2, 1, 5, 4}

आउटपुट: व्यवस्था से पहले सरणी: 0 3 2 1 5 4 O(1) अतिरिक्त स्थान के साथ arr[i] arr[arr[i]] बन जाए ऐसा सरणी का पुनर्व्यवस्थित रूप: 0 1 2 3 4 5

व्याख्या: हमें आकार 6 की एक पूर्णांक सरणी दी गई है और सरणी के सभी तत्वों का मान 6 से कम है। अब, हम सरणी को पुनर्व्यवस्थित करेंगे: arr[arr[0]] 0 है, arr[arr[1]] 1 है, arr[arr[2]] 2 है, arr[arr[3]] 3 है, arr[arr[4]] 4 है और arr[arr[5]] 5 है। इसलिए, पुनर्व्यवस्था के बाद अंतिम सरणी 0 1 2 3 4 5 है।

इनपुट: int arr[] = {1, 0}

आउटपुट: व्यवस्था से पहले सरणी: 1 0 O(1) अतिरिक्त स्थान के साथ arr[i] arr[arr[i]] बन जाए ऐसा सरणी का पुनर्व्यवस्थित रूप: 0 1

व्याख्या: हमें आकार 2 की एक पूर्णांक सरणी दी गई है और सरणी के सभी तत्वों का मान 2 से कम है। अब, हम सरणी को पुनर्व्यवस्थित करेंगे: arr[arr[0]] 1 है और arr[arr[1]] 0 है। इसलिए, पुनर्व्यवस्था के बाद अंतिम सरणी 0 1 है।

इनपुट: int arr[] = {1, 0, 2, 3}

आउटपुट: व्यवस्था से पहले सरणी: 1 0 2 3 O(1) अतिरिक्त स्थान के साथ arr[i] arr[arr[i]] बन जाए ऐसा सरणी का पुनर्व्यवस्थित रूप: 0 1 2 3

व्याख्या: हमें आकार 4 की एक पूर्णांक सरणी दी गई है और सरणी के सभी तत्वों का मान 4 से कम है। अब, हम सरणी को पुनर्व्यवस्थित करेंगे: arr[arr[0]] 0 है, arr[arr[1]] 1 है, arr[arr[2]] 2 है और arr[arr[3]] 3 है। इसलिए, पुनर्व्यवस्था के बाद अंतिम सरणी 0 1 2 3 है।

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण:

  • पूर्णांक प्रकार के तत्वों की एक सरणी इनपुट करें और सरणी का आकार गणना करें।
  • व्यवस्था से पहले सरणी प्रिंट करें और फंक्शन Rearrangement(arr, size) को कॉल करें।
  • फंक्शन Rearrangement(arr, size) के अंदर:
    • i को 0 से size से कम तक लूप चलाएं। अंदर, temp को arr[arr[i]] % size पर सेट करें और arr[i] += temp * size।
    • i को 0 से size से कम तक लूप चलाएं। अंदर, arr[i] = arr[i] / size सेट करें।
  • परिणाम प्रिंट करें।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

void Rearrangement(int arr[], int size) {
    for(int i = 0; i < size; i++) {
        int temp = arr[arr[i]] % size;
        arr[i] += temp * size;
    }
    for(int i = 0; i < size; i++) {
        arr[i] = arr[i] / size;
    }
}

int main() {
    // एक सरणी इनपुट करें
    int arr[] = {0, 3, 2, 1, 5, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    // मूल सरणी प्रिंट करें
    cout << "Array before Arrangement: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    // सरणी को पुनर्व्यवस्थित करने के लिए फंक्शन कॉल करें
    Rearrangement(arr, size);
    // मानों को पुनर्व्यवस्थित करने के बाद सरणी प्रिंट करें
    cout << "\nRearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: ";
    for(int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:

Array before Arrangement: 0 3 2 1 5 4
Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5
  1. - O(n) समय और O(1) अतिरिक्त स्पेस में ऐरे में डुप्लीकेट खोजें C++ में

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

  1. - 0 से N-1 तत्वों वाले स्थिर ऐरे में O(1) स्पेस में डुप्लीकेट खोजें C++ में

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

  1. - C++ में पूर्णांकों की सरणी में अधिकतम गुणनफल वाली जोड़ी ढूंढें

    समस्या विवरण एक सरणी A दी गई है जिसमें n तत्व हैं (सकारात्मक और नकारात्मक दोनों)। हमें एक जोड़ी (x, y) ढूंढनी है जिसका गुणनफल अधिकतम हो। उदाहरण के लिए, सरणी A = [-1, -4, -3, 0, 2, -5] के लिए, अधिकतम गुणनफल वाली जोड़ी (-4, -5) होगी क्योंकि उनका गुणनफल 20 है। हल दृष्टिकोण हमें चार मान ट्रैक करने हों