क्रमपरिवर्तन Leetcode Solution


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब वीरांगना सेब Atlassian ब्लूमबर्ग ByteDance ईबे Facebook Garena पिताजी जाओ गोल्डमैन सैक्स गूगल लिंक्डइन माइक्रोसॉफ्ट ओरेकल Salesforce एसएपी Uber VMware वॉलमार्ट लैब्स याहू
बैक ट्रैकिंग

समस्या क्रमपरिवर्तन Leetcode Solution पूर्णांकों का एक सरल अनुक्रम प्रदान करता है और हमें एक पूर्ण वेक्टर या वापस करने के लिए कहता है सरणी दिए गए अनुक्रम के सभी क्रमपरिवर्तन। तो, समस्या को हल करने से पहले। हमें क्रमपरिवर्तन से परिचित होना चाहिए। तो, एक क्रमपरिवर्तन कुछ नहीं बल्कि दिए गए पूर्णांकों की व्यवस्था है। इसलिए, जब हम कहते हैं कि हमें अनुक्रम के सभी क्रमपरिवर्तन की आवश्यकता है। हमारा मतलब है कि हमें दिए गए अनुक्रम की सभी संभावित व्यवस्थाओं को प्रिंट या वापस करना आवश्यक है। आइए बेहतर समझ के लिए कुछ उदाहरण देखें।

Given sequence: [1,2,3]
Permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

स्पष्टीकरण: सभी तरीके जो आप एक अनुक्रम में 1, 2, 3 लिख सकते हैं, आउटपुट के रूप में दिए गए हैं। क्रमपरिवर्तन में 6, 1, 2 लिखने के कुल 3 तरीके हैं।

[0,1]
[[0,1],[1,0]]

स्पष्टीकरण: 2, 0 लिखने के लिए केवल 1 तरीके संभव हैं।

क्रमपरिवर्तन Leetcode समाधान के लिए दृष्टिकोण

क्रमपरिवर्तन Leetcode Solution

समस्या क्रमपरिवर्तन Leetcode Solution ने हमें दिए गए अनुक्रम के सभी क्रमपरिवर्तन उत्पन्न करने के लिए कहा। आमतौर पर, हमें एक क्रमपरिवर्तन की आवश्यकता होती है या कुछ अनुक्रम पुनरावृत्ति जाने के लिए महत्वपूर्ण है। लेकिन यहाँ पुनरावृत्ति या पीछे हटना थोड़ा मुश्किल है। एक तरीका यह हो सकता है कि किसी तत्व को किसी तत्व से उठाकर उत्तर के अंत में रखा जा सकता है। इस तरह एक क्रमचय उत्पन्न होता है और किसी तरह यह याद रखना सुनिश्चित करें कि यह क्रमचय उत्पन्न हो गया है और इसे दोहराया नहीं जाना चाहिए। लेकिन ऐसा करने के बजाय, हम कार्य करने का एक सरल तरीका खोजने की कोशिश करते हैं। क्या होगा अगर हम एक तत्व को चुनते हैं और इसे वर्तमान तत्व के साथ स्वैप करते हैं। फिर वर्तमान सूचकांक के बाद अनुक्रम एक सूचकांक के लिए सभी क्रमपरिवर्तन उत्पन्न करने के लिए एक पुनरावर्ती कॉल करें।

एक बार जब हम क्रमबद्धता एक सूचकांक को आगे बढ़ाने के साथ किया जाता है। हम चुने हुए तत्व को हटा देते हैं, और फिर एक और तत्व चुनते हैं और प्रक्रिया को दोहराते हैं। इस तरह हम सुनिश्चित करते हैं कि हमने प्रत्येक अप्रयुक्त तत्व को कम से कम एक बार वर्तमान स्थिति में रखा है। और जब से हमने एक छोटे उपप्रकार के लिए एक पुनरावर्ती कॉल किया। छोटे उपप्रकार के अनुक्रम के लिए क्रमचय का उत्पादन किया जा रहा है जो वर्तमान सूचकांक के ठीक बाद शुरू होता है। उन क्रमचयों को वर्तमान क्रमपरिवर्तन में जोड़ने से वर्तमान सूचकांक पर एक तत्व सेट के साथ क्रमपरिवर्तन का एक सेट पूरा होता है। इस तरह हम सरणी को बाईं से दाईं ओर रखते हैं और समस्या को छोटे उपप्रकारों में विभाजित करते हैं। एक बार जब हम आवश्यकता पर पहुँच जाते हैं तो हमने दा संभव क्रमचय उत्पन्न कर दिया है और हम इसे उत्तर में जोड़ देते हैं।

पीछे का कोड

क्रमपरिवर्तन के लिए सी ++ कोड Leetcode Solution

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

void permutationUtil(vector<int> &nums, int i, int &numsSize, vector<vector<int>> &answer){
    if(i == numsSize){
        answer.push_back(nums);
    }
    for(int j = i; j < numsSize; j++){
        swap(nums[i], nums[j]);
        permutationUtil(nums, i+1, numsSize, answer);
        swap(nums[i], nums[j]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> answer;
    int numsSize = nums.size();
    permutationUtil(nums, 0, numsSize, answer);
    return answer;
}

int main(){
    vector<int> nums({1, 2, 3});
    vector<vector<int>> answer = permute(nums);
    for(auto i: answer){
        for(auto j: i)
            cout<<j<<" ";
        cout<<"\t";
    }
}
1 2 3   1 3 2   2 1 3   2 3 1   3 2 1   3 1 2

पेर्मोटेशन लेटकोड सॉल्यूशन के लिए जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
    public static void permutationUtil(List<Integer> nums, int i, int numsSize, List<List<Integer>> answer){
        if(i == numsSize){
            answer.add(new ArrayList<Integer>(nums));
        }
        for(int j = i; j < numsSize; j++){
            Collections.swap(nums, i, j);
            permutationUtil(nums, i+1, numsSize, answer);
            Collections.swap(nums, i, j);
        }
    }
 
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new LinkedList();
        int numsSize = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<numsSize;i++)
            list.add(nums[i]);
        permutationUtil(list, 0, numsSize, answer);
        return answer;
    }
 
    public static void main(String[] args){
    	int nums[] = {1, 2, 3};
    	List<List<Integer>> answer = permute(nums);
    	System.out.println(answer.toString());
    }
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

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

समय जटिलता

ओ (सिग्मा (पी (एन, के))), जहां P n या आंशिक क्रमपरिवर्तन का k क्रमपरिवर्तन है। अधिक औपचारिक रूप से, पी (एन, के) = (एन!) / ((एनके)!)।

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

पर!), चूँकि हमें सभी संभव समाधानों को संगृहीत करना है जो N हैं! आकार में जहां N सरणी का आकार है।