ಅರೇ [i] ನಾನು ಸಮನಾಗಿರುವ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಮರುಹೊಂದಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಸೆಂಚರ್ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಫ್ಯಾನಟಿಕ್ಗಳು ಫೋರ್‌ಕೈಟ್‌ಗಳು ಜೊಹೊ
ಅರೇ ಹ್ಯಾಶ್

“ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಮರುಹೊಂದಿಸಿ ಅಂದರೆ arr [i] = i” ಸಮಸ್ಯೆ ನಿಮಗೆ 0 ರಿಂದ n-1 ವರೆಗಿನ ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಎಲ್ಲಾ ಅಂಶಗಳು ರಚನೆಯಲ್ಲಿ ಇಲ್ಲದಿರುವುದರಿಂದ, ಅವುಗಳ ಸ್ಥಳದಲ್ಲಿ -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 ಮತ್ತು ಅರ್ [3] = 3 ಮತ್ತು 1 ರಿಂದ 0 ರ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಯಾವುದೇ ಸಂಖ್ಯೆಗಳು ಇಲ್ಲದಿದ್ದರೆ ಉಳಿದ ಸ್ಥಳಗಳನ್ನು -4 ಎಂದು ಗುರುತಿಸಲಾಗುತ್ತದೆ.

ನಾವು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಿದ್ದೇವೆ. ನಮ್ಮ ಮುಖ್ಯ ಆಲೋಚನೆಯೆಂದರೆ “ಅರೇ [i] = i” ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ರಚನೆಯ ಅಂಶಗಳನ್ನು ಸ್ವ್ಯಾಪ್ ಮಾಡುವುದು. ನಾವು ಶ್ರೇಣಿಯನ್ನು 0 ರಿಂದ n-1 ರವರೆಗೆ ಹಾದುಹೋಗಲಿದ್ದೇವೆ ಮತ್ತು “i” ನ ಪ್ರತಿಯೊಂದು ಮೌಲ್ಯವನ್ನು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅರ್ [i] 0 ಗಿಂತ ಹೆಚ್ಚಿದ್ದರೆ ನಾವು ಅದನ್ನು ತಪ್ಪಿಸಬಹುದು ನಕಾರಾತ್ಮಕ ಸಂಖ್ಯೆಗಳು. ಅಲ್ಲಿ ಅನ್ವಯಿಸುವ ಒಂದು ಷರತ್ತು ಸಹ ಇದೆ, ಇದರಿಂದಾಗಿ ಲೂಪ್ ಅನಂತವಾಗಿ ಹೋಗುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ನಾವು 'ಐ' ಮೌಲ್ಯವನ್ನು ಬೇರೆ ಭಾಗದಲ್ಲಿ ಹೆಚ್ಚಿಸುತ್ತಿದ್ದೇವೆ, ಆದ್ದರಿಂದ ನಾವು ಆರ್ [ಐ] ಸಹ "ನಾನು" ಗೆ ಸಮನಾಗಿರಬಾರದು ಎಂದು ಪರಿಶೀಲಿಸುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಅದು ಬಿಟ್ಟುಬಿಡಬಹುದು ಮತ್ತು ಮತ್ತಷ್ಟು ಚಲಿಸಬಹುದು ಮತ್ತು ಹೆಚ್ಚಿನ ಮೌಲ್ಯಗಳನ್ನು ಪರಿಶೀಲಿಸಬಹುದು.

0 ಗೆ ಸಮನಾಗಿರುವ ಮತ್ತು i ಗೆ ಸಮನಾಗಿರದ ಆ ಮೌಲ್ಯಗಳನ್ನು ನಾವು ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಬೇಕು. ಅಲ್ಲದೆ, ನಾವು ಶ್ರೇಣಿಯೊಳಗೆ ಒಂದೇ ಲೂಪ್‌ನೊಂದಿಗೆ, ಒಂದು ಶ್ರೇಣಿಯೊಳಗೆ ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳುತ್ತಿದ್ದೇವೆ, ಅದಕ್ಕಾಗಿಯೇ ನಾವು ಸ್ವ್ಯಾಪ್ ಮಾಡಲು ಅರ್ [i] ಮೌಲ್ಯಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ತೆಗೆದುಕೊಂಡಿದ್ದೇವೆ. ಮತ್ತು ಅಂತಿಮವಾಗಿ ರಚನೆಯ ಆ ಮೌಲ್ಯಗಳನ್ನು ಮುದ್ರಿಸಿ.

Ar [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]

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ನಾವು ಕೇವಲ ಶ್ರೇಣಿಯನ್ನು ದಾಟುತ್ತಿದ್ದರಿಂದ, ನಾವು ರೇಖೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸಾಧಿಸಿದ್ದೇವೆ. ಒ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ಅರೇ [i] = i ”ಸಮಸ್ಯೆಯಂತಹ ಶ್ರೇಣಿಯನ್ನು ಮರುಹೊಂದಿಸಿ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಅಲ್ಗಾರಿದಮ್ ಸ್ವತಃ O (1) ಸ್ಥಿರ ಸ್ಥಳವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಆದರೆ ಇನ್ಪುಟ್ ಅನ್ನು ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಿರುವುದರಿಂದ. ನಾವು ಪಡೆಯುತ್ತೇವೆ ಒ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.