ஒரு வரிசையை மறுசீரமைக்கவும் இது அர் [i] எனக்கு சமம்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அக்சன்சர் அடோப் அமேசான் வெறியர்கள் ஃபோர்கைட்டுகள் ஸோகோ
அணி ஹாஷ்

"0 முதல் n-1 வரையிலான முழு எண்களின் வரிசை உங்களுக்கு வழங்கப்படுவதாக arr [i] = i" சிக்கல் கூறுகிறது. அனைத்து கூறுகளும் வரிசையில் இல்லை என்பதால், அவற்றுக்கு பதிலாக -1 உள்ளது. வரம்பிற்கு இடையில் ஒரு எண் ஒரு வரிசையில் இல்லாவிட்டால், வரிசையை மறுசீரமைக்க சிக்கல் அறிக்கை கேட்கிறது, பின்னர் அதை -1 எனக் குறிக்கவும், உறுப்புகளை arr [i] = i என மறுசீரமைக்கவும்.

உதாரணமாக

arr[]={9,4,-1,-1,2,7,8,1,5,-1}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

விளக்கம்: ஏதேனும் என்பதால் உறுப்பு வரம்பிற்குள் இல்லை பின்னர், அது -1 உடன் மாற்றப்பட்டது மற்றும் வரிசைக் குறியீடு எண்ணுடன் மாற்றப்படுகிறது.

ஒரு வரிசையை மறுசீரமைப்பதற்கான வழிமுறை அர் [i] சமம் i

1. Traverse the array from 0 to n-1(length of the array).
2. Check if arr[i] is greater than equal to 0 and not equal to i.
    1. Swap the elements by doing the following steps.
        1. temp = arr[arr[i]]
        2. arr[arr[i]] = arr[i]
        3. arr[i] = temp
3. Else increase the value of i.
4. Print the array.

விளக்கம்

எங்களுக்கு ஒரு வழங்கப்படுகிறது வரிசை of முழு அளவு n. இது o முதல் n-1 வரம்பிற்குள் இருக்கும் எண்களைக் கொண்டிருக்கும். அவற்றில் சில எண்களைக் காணவில்லை வரம்பிலிருந்து. Ar [i] ஐ மதிப்பாக மாற்றும் அனைத்து உறுப்புகளையும் மாற்றுமாறு கேட்டுள்ளோம். வரிசையில் எந்த எண்ணும் இல்லை என்றால், அதை -1 உடன் மாற்ற வேண்டும். நாம் 0 முதல் 4 வரையிலான வரம்பைக் கொண்டிருக்கிறோம் என்று வைத்துக்கொள்வோம், இதில் நாம் ஒரு வரிசையில் 2 மற்றும் 3 மட்டுமே இருக்கிறோம், மீதமுள்ளவை -1 உறுப்புகளாக இருந்தால், நாம் குறியீட்டில் 2 மற்றும் 3 ஐ அர் [2] = ஆக வைக்க வேண்டும். 2 மற்றும் arr [3] = 3 மற்றும் 1 முதல் 0 வரையிலான எண்களில் ஏதேனும் எண்கள் இல்லாவிட்டால், மீதமுள்ள இடங்கள் -4 என குறிக்கப்படும்.

நாங்கள் ஒரு வரிசையை வழங்கியுள்ளோம். எங்கள் முக்கிய யோசனை என்னவென்றால், "[[]] = i" சிக்கலைத் தீர்க்க ஒரு வரிசையை மறுசீரமைக்கவும். நாம் வரிசையை 0 முதல் n-1 வரை பயணிக்கப் போகிறோம், மேலும் “i” இன் ஒவ்வொரு மதிப்பையும் சரிபார்க்கிறோம். அர் [i] 0 ஐ விட அதிகமாக இருந்தால், அதைத் தவிர்க்கலாம் எதிர்மறை எண்கள். வேறு ஒரு பகுதியிலும் 'நான்' இன் மதிப்பை அதிகரித்து வருவதால், வளையம் எல்லையற்றதாக இருக்கக்கூடாது என்பதற்காக அங்கே ஒரு நிபந்தனையும் உள்ளது, ஆகவே, அர் [i] “நான்” க்கு சமமாக இருக்கக்கூடாது என்பதையும் சரிபார்க்கிறோம். இதனால் அது தவிர்க்கவும் மேலும் நகர்த்தவும் மேலும் மதிப்புகளை சரிபார்க்கவும் முடியும்.

0 க்கு சமமான மற்றும் i க்கு சமமாக இல்லாத அந்த மதிப்புகளை நாம் மாற்ற வேண்டும். மேலும், நாங்கள் வரிசைக்குள் ஒரு வளையத்துடன், ஒரு வரம்பிற்குள் இடமாற்றம் செய்கிறோம், அதனால்தான் இடமாற்றம் செய்ய ar [i] மதிப்புகளின் வரிசையை எடுத்துள்ளோம். கடைசியாக வரிசையின் அந்த மதிப்புகளை அச்சிடுங்கள்.

Ar [i] = i போன்ற ஒரு வரிசையை மறுசீரமைக்கவும்

நடைமுறைப்படுத்தல்

ஒரு வரிசையை மறுசீரமைக்க சி ++ நிரல் அர் [i] சமம் i

#include<iostream>

using namespace std;

void arrayRearrange(int arr[], int n)
{
    for (int i = 0; i < n;)
    {
        if (arr[i] >= 0 && arr[i] != i)
        {
            int temp = arr[arr[i]];
            arr[arr[i]] = arr[i];
            arr[i] = temp;
        }
        else
        {
            i++;
        }
    }
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
}
int main()
{
    int arr[] = {9,4,-1,-1,2,7,8,1,5,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    arrayRearrange(arr,n);

    return 0;
}
-1 1 2 -1 4 5 -1 7 8 9

ஒரு வரிசையை மறுசீரமைக்க ஜாவா நிரல் அர் [i] சமம் i

import java.util.Arrays;

class arrayRearrange
{
    public static void main(String[] args)
    {
        int[] arr = {9,4,-1,-1,2,7,8,1,5,-1};
        for (int i = 0; i < arr.length;)
        {
            if (arr[i] >= 0 && arr[i] != i)
            {
                int temp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] = temp;
            }
            else
            {
                i++;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
[-1, 1, 2, -1, 4, 5, -1, 7, 8, 9]

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

நாங்கள் வரிசையை கடந்து செல்வதால், நேரியல் நேர சிக்கலை அடைந்தோம். ஓ (என்) எங்கே “என்” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை “ar [i] = i” சிக்கல் போன்ற ஒரு வரிசையை மறுசீரமைக்கவும்.

விண்வெளி சிக்கலானது

வழிமுறை O (1) நிலையான இடத்தை எடுக்கும், ஆனால் உள்ளீடு ஒரு வரிசையில் சேமிக்கப்படுவதால். நாங்கள் பெறுகிறோம் ஓ (என்) எங்கே “என்” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.