ರಚನೆಯಲ್ಲಿನ ಒಂದು ಅಂಶದ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕಗಳ ನಡುವಿನ ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಕೋಲೈಟ್ ಅಮೆಜಾನ್ ಪಾದಯಾತ್ರೆ MakeMyTrip ಓಲಾ ಕ್ಯಾಬ್ಸ್ ಎಸ್‌ಎಪಿ ಲ್ಯಾಬ್‌ಗಳು
ಅರೇ ಹ್ಯಾಶ್

ನೀವು ಒಂದು ಹೊಂದಿದ್ದೀರಿ ಎಂದು ಭಾವಿಸೋಣ ಸರಣಿ of ಪೂರ್ಣಾಂಕಗಳು. “ಶ್ರೇಣಿಯಲ್ಲಿನ ಒಂದು ಅಂಶದ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕಗಳ ನಡುವಿನ ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸ” ಎಂಬ ಸಮಸ್ಯೆಯು ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಪ್ರತಿ ಸಂಖ್ಯೆಯ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕದ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ, ಅಂದರೆ ವ್ಯತ್ಯಾಸವು ಎಲ್ಲಕ್ಕಿಂತ ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ.

ಉದಾಹರಣೆ

arr[] =  {2, 3, 5, 1, 4, 6, 2, 5};
6

ವಿವರಣೆ

2 ರ ಮೊದಲ ಸೂಚ್ಯಂಕ → 0

2 ರ ಕೊನೆಯ ಸೂಚ್ಯಂಕ → 6

ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸ (6-0) = 6

ರಚನೆಯಲ್ಲಿನ ಒಂದು ಅಂಶದ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕಗಳ ನಡುವಿನ ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸ

arr[] =  {2, 3, 6, 5, 4, 5, 1, 4};
3

ವಿವರಣೆ

4 ರ ಮೊದಲ ಸೂಚ್ಯಂಕ → 4

4 ರ ಕೊನೆಯ ಸೂಚ್ಯಂಕ → 7

ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸ (7-4) = 3

ಕ್ರಮಾವಳಿ

  1. ಇಡೀ ಸಂಚರಿಸಿ ಸರಣಿ.
  2. ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಆರಿಸಿ ಮತ್ತು ಅದರ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಅಂಶವನ್ನು ಪಡೆಯಿರಿ ಮತ್ತು ಅದನ್ನು ಹ್ಯಾಶ್‌ಟೇಬಲ್‌ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ.
  3. ಸಂಚರಿಸಿ ನಕ್ಷೆ:
    1. ಪ್ರತಿ ಅಂಶದ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕದ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ.
    2. ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು ಕೆಲವು ವೇರಿಯೇಬಲ್ ಆಗಿ ಸಂಗ್ರಹಿಸಿ ಮತ್ತು ಹಿಂದಿನ ಮೌಲ್ಯಕ್ಕಿಂತ ಗರಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ನೀವು ಕಂಡುಕೊಂಡಾಗಲೆಲ್ಲಾ ಅದನ್ನು ನವೀಕರಿಸಿ.
  4. ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು ಹಿಂತಿರುಗಿ.

ವಿವರಣೆ

ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಪೂರ್ಣಾಂಕ ರಚನೆ, ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಮೌಲ್ಯದ ಮೊದಲ ಸೂಚ್ಯಂಕ ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕದ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕು. ಅದರ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕದ ನಡುವಿನ ಯಾವುದೇ ಸಂಖ್ಯೆಯ ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ. ಇದಕ್ಕಾಗಿ, ನಾವು ಬಳಸಲಿದ್ದೇವೆ ಹ್ಯಾಶಿಂಗ್. ನಾವು ಒಂದು ಶ್ರೇಣಿಯ ಅಂಶವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಅದರ ಮೊದಲ ಸೂಚ್ಯಂಕ ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕವನ್ನು ಕಂಡುಹಿಡಿಯುತ್ತೇವೆ ಅಥವಾ ಅದು ಮೊದಲು ಮತ್ತು ಕೊನೆಯದಾಗಿ ಸಂಭವಿಸಿದಾಗ.

ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಮತ್ತು ಅವುಗಳ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚಿಯನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಇರಿಸಿದ ನಂತರ ನಕ್ಷೆಯಲ್ಲಿ ಸಂಚರಿಸಿ. ಈಗ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಆರಿಸಿ ನಂತರ ಅವುಗಳ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚಿಯನ್ನು ತೆಗೆದುಕೊಳ್ಳಿ ಮತ್ತು ಅದು ಎಲ್ಲಕ್ಕಿಂತ ಗರಿಷ್ಠವಾಗಿರಬೇಕು ಎಂಬ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ನಾವು ವೇರಿಯಬಲ್ ಅನ್ನು ಬಳಸಬಹುದು ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸ ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು ಗಮನಿಸಲು. ಪ್ರತಿಯೊಂದು ಅಂಶದ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚಿಯನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ವರ್ಗ ಮತ್ತು ಅದರ ವಸ್ತುವನ್ನು ಬಳಸುತ್ತೇವೆ.

ನಾವು ಒಂದು ಉದಾಹರಣೆಯನ್ನು ಪರಿಗಣಿಸೋಣ:

ಉದಾಹರಣೆ

ಅರ್ [] = {2, 3, 5, 1, 4, 6, 2, 5}

ನಮ್ಮಲ್ಲಿ ಅರೇ ಇನ್‌ಪುಟ್ ಇದೆ. ಇದನ್ನು ಪರಿಹರಿಸಲು ನಾವು ಒಂದು ವರ್ಗವನ್ನು ಬಳಸುತ್ತೇವೆ. ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಮೊದಲ ಬಾರಿಗೆ ಹಾದುಹೋಗುತ್ತಿದ್ದರೆ ನಾವು ಅದನ್ನು ನೋಡುತ್ತೇವೆ. ನಂತರ ನಾವು ಅದರ ಸೂಚಿಯನ್ನು ಮೊದಲ ಸೂಚ್ಯಂಕವಾಗಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ ಮತ್ತು ಅದೇ ಅಂಶವು ಮತ್ತೆ ಬಂದಾಗ. ನಂತರ ಪ್ರತಿ ಬಾರಿ ನಾವು ಅದರ ಸೂಚಿಯನ್ನು ಎರಡನೇ ಸೂಚ್ಯಂಕವಾಗಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಈ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು, ನಮ್ಮಲ್ಲಿ ನಕ್ಷೆ ಇದೆ:

ನಕ್ಷೆ: 1-> 3: ಶೂನ್ಯ,

2-> 0: 6,

3-> 1, ಶೂನ್ಯ,

4-> 4: ಶೂನ್ಯ,

5-> 2: 7,

6-> 5: ಶೂನ್ಯ

ನಾವು ನಕ್ಷೆಯನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ, ಮತ್ತು ನಾವು ಪ್ರತಿ ಮೌಲ್ಯವನ್ನು ತೆಗೆದುಕೊಂಡು ಅವುಗಳ ಸೂಚ್ಯಂಕಗಳ ವ್ಯತ್ಯಾಸಗಳನ್ನು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಶೂನ್ಯ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ಮೌಲ್ಯಗಳನ್ನು ನಾವು ನಿರ್ಲಕ್ಷಿಸಲಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ನಾವು 2 ಮತ್ತು 5 ಅನ್ನು ಹೊಂದಿದ್ದೇವೆ ಮತ್ತು ಅದರಲ್ಲಿ 2 ಅದರ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚ್ಯಂಕಕ್ಕಿಂತ ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು (6) ಹೊಂದಿದೆ 5 ಇದು ವ್ಯತ್ಯಾಸವನ್ನು ಹೊಂದಿದೆ (5). ಆದ್ದರಿಂದ ನಾವು 6 ಅನ್ನು ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸವಾಗಿ ಹಿಂದಿರುಗಿಸಲಿದ್ದೇವೆ ಮತ್ತು ಅದು ನಮ್ಮ ಉತ್ತರವಾಗಿರುತ್ತದೆ.

ರಚನೆಯಲ್ಲಿನ ಒಂದು ಅಂಶದ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚಿಕೆಗಳ ನಡುವೆ ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#include<bits/stdc++.h>

using namespace std;

int maxDifference(int arr[], int n)
{
    struct IndexValue
    {
        int fir, last;
    };
    unordered_map<int, IndexValue> MAP;
    for (int i=0; i<n; i++)
    {
        if (MAP.find(arr[i]) == MAP.end())
            MAP[arr[i]].fir = i;

        MAP[arr[i]].last = i;
    }

    int difference, differenceIndex = INT_MIN;

    unordered_map<int, IndexValue>::iterator itr;
    for (itr=MAP.begin(); itr != MAP.end(); itr++)
    {
        difference = (itr->second).last - (itr->second).fir;
        if (differenceIndex < difference)
            differenceIndex = difference;
    }
    return differenceIndex;
}
int main()
{
    int arr[] = {2, 3, 5, 1, 4, 6, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference b/w the first and last index of a number= "<<maxDifference(arr, n);
    return 0;
}
Maximum difference b/w the first and last index of a number= 6

ಶ್ರೇಣಿಯಲ್ಲಿನ ಒಂದು ಅಂಶದ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಸೂಚಿಕೆಗಳ ನಡುವೆ ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

import java.util.HashMap;
import java.util.Map;

class IndexValue
{
    int first;
    int second;
    public IndexValue()
    {
        super();
    }
}
class DifferenceOfIndexes
{
    private static int getIndexesDifferent(int[] arr)
    {
        int n = arr.length;
        int differenceIndex = 0;
        Map<Integer, IndexValue> MAP = new HashMap<Integer, IndexValue>();

        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]))
            {
                IndexValue iv = MAP.get(arr[i]);
                iv.second = i;
            }
            else
            {
                IndexValue iv = new IndexValue();
                iv.first = i;
                MAP.put(arr[i], iv);
            }
        }
        for (Map.Entry<Integer, IndexValue> entry : MAP.entrySet())
        {
            IndexValue iv = entry.getValue();
            if ((iv.second - iv.first) > differenceIndex)
            {
                differenceIndex = iv.second - iv.first;
            }
        }
        return differenceIndex;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,5,1,4,6,2,5};
        System.out.println("Maximum difference b/w the first and last index of a number= "+ getIndexesDifferent(arr));
    }
}
Maximum difference b/w the first and last index of a number= 6

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

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

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್ ' ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ

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

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್ ' ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ