ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಪ್ರಸ್ತುತ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಗಳು


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

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

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

ಉದಾಹರಣೆ

arr[] = {2, 24, 30, 26, 99, 25}
3

ವಿವರಣೆ: ಸತತ ಸಂಖ್ಯೆಗಳು ⇒ 24, 25, 26 (3 ರ ಸೆಟ್).

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

ವಿವರಣೆ: ಸತತ ಸಂಖ್ಯೆಗಳು ⇒ -6, -5 (2 ರ ಸೆಟ್).

ಕ್ರಮಾವಳಿ

1. Declare a set.
2. Do traversing of the array, and insert all the values of array into the Set.
3. Set output to 0.
4. Traverse the array from i=0, to i<n(length of the array).
  1. Check if Set contains the arr[i].
    1. If true, then pick the current array element and store it to temp.
  2. While Set contains the temp, repeatedly increases the values of temp.
  3. Find out the maximum between output and temp-arr[i] and store it into the output.
5. Return output.

ವಿವರಣೆ

ನೀಡಲಾಗಿದೆ ಪೂರ್ಣಾಂಕ ಸರಣಿ, ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಸತತ ಸಂಖ್ಯೆಗಳ ಅತ್ಯಧಿಕ ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ. ನಾವು a ಅನ್ನು ಬಳಸಲಿದ್ದೇವೆ ಸೆಟ್. ಸೆಟ್ ಇದೇ ರೀತಿಯ ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕುವ ವೈಶಿಷ್ಟ್ಯವನ್ನು ಒದಗಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ಸಾಮಾನ್ಯ ಅಂಶವನ್ನು ನಿರ್ವಹಿಸುವ ಬಗ್ಗೆ ನಾವು ಚಿಂತಿಸಬೇಕಾಗಿಲ್ಲ, ಅದನ್ನು ಸ್ವಯಂಚಾಲಿತವಾಗಿ ನಿರ್ವಹಿಸಲಾಗುತ್ತದೆ.

ನಾವು ರಚನೆಯ ಎಲ್ಲಾ ಮೌಲ್ಯಗಳನ್ನು ಸೆಟ್ಗೆ ಸೇರಿಸಲಿದ್ದೇವೆ. ಏಕೆಂದರೆ ನಂತರ, ನಾವು ಸತತ ಸಂಖ್ಯೆಗಳನ್ನೂ ಪರಿಶೀಲಿಸಲಿದ್ದೇವೆ. ನಾವು ಮತ್ತೆ ರಚನೆಯನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ, ಪ್ರತಿ ಅಂಶವನ್ನು ಆರಿಸಿಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಪರಿಶೀಲಿಸುತ್ತೇವೆ ನಕ್ಷೆ ಅದು ನಿಜವಾಗಿದ್ದರೆ, ನಾವು ಆ ಅಂಶವನ್ನು ತಾತ್ಕಾಲಿಕ ವೇರಿಯೇಬಲ್ ಆಗಿ ಆರಿಸಲಿದ್ದೇವೆ ಮತ್ತು ನಕ್ಷೆಯಲ್ಲಿ ಆ ಟೆಂಪ್ ಇದ್ದರೆ, ಮತ್ತೆ ನಿಜವಾಗಿದ್ದರೆ, ಟೆಂಪ್ ಮೌಲ್ಯವನ್ನು 1 ರಿಂದ ಹೆಚ್ಚಿಸಿ, ನಂತರ ಮತ್ತೆ ಪರಿಶೀಲಿಸಿ, ಮತ್ತು ಮತ್ತೆ ಅದನ್ನು ಹೆಚ್ಚಿಸಿ, ನಕ್ಷೆಯಲ್ಲಿ ಹೆಚ್ಚಿದ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರದವರೆಗೆ ಇದನ್ನು ಮುಂದುವರಿಸಿ. ಈಗ, ನಾವು ಈ ಲೂಪ್‌ನಿಂದ ಹೊರಬಂದಾಗ, ನಕ್ಷೆಯಲ್ಲಿರುವ ಪ್ರಸ್ತುತ ರಚನೆಯ ಅಂಶದ ಹೆಚ್ಚಿನ ವರ್ಧಿತ ಮೌಲ್ಯವನ್ನು ನಾವು ಮಾಡುತ್ತೇವೆ, ಅದನ್ನು ನಾವು 1 ರ ಎಣಿಕೆ ಮೂಲಕ ಹೆಚ್ಚಿಸುತ್ತೇವೆ, ಆದ್ದರಿಂದ ಇದು ಸತತ ಸಂಖ್ಯೆಗಳೂ ಆಗಿರುತ್ತದೆ.

ನಾವು ಈಗ ಗರಿಷ್ಠ output ಟ್‌ಪುಟ್ ಮತ್ತು ಟೆಂಪ್-ಆರ್ [i] ನ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ, ಈ ವ್ಯತ್ಯಾಸವು ಎಣಿಕೆಯ ತಪ್ಪಾದ ಸಂಖ್ಯೆಯನ್ನು ನೀಡುತ್ತದೆ ಎಂದು ಯೋಚಿಸಬೇಡಿ, ಏಕೆಂದರೆ ನಾವು ಹೊರಬರುವಾಗ ಟೆಂಪ್‌ನ ಹೆಚ್ಚಿದ ಮೌಲ್ಯವನ್ನು ಪಡೆಯುತ್ತೇವೆ ಲೂಪ್, ಸತತ ಸಂಖ್ಯೆಗಳ ಸರಿಯಾದ ಎಣಿಕೆಯನ್ನು ನಾವು ಪಡೆಯುತ್ತೇವೆ. ನಾವು ನಂತರ output ಟ್‌ಪುಟ್ ಮತ್ತು ಟೆಂಪ್-ಆರ್ [i] (output ಟ್‌ಪುಟ್, ಟೆಂಪ್-ಆರ್ [ಐ]) ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಅರ್ರ್ [i] ಸತತ ಸಂಖ್ಯೆಗಳ ಸರಣಿಯ ಆರಂಭಿಕ ಹಂತ ಮತ್ತು ತಾತ್ಕಾಲಿಕ, ಅಂತ್ಯದ ಬಿಂದು. ಇಡೀ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುವಾಗ ಗರಿಷ್ಠ output ಟ್‌ಪುಟ್ ಅನ್ನು ನಾವು ಕಂಡುಕೊಳ್ಳುವವರೆಗೆ ಈ ಹಂತಗಳನ್ನು ಪುನರಾವರ್ತಿಸಲಾಗುತ್ತದೆ.

ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಪ್ರಸ್ತುತ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಗಳು

ಅನುಷ್ಠಾನ

ಅರೇನಲ್ಲಿ ಪ್ರಸ್ತುತ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include<iostream>
#include<unordered_set>

using namespace std;

int getMaxConsecutiveNumber(int arr[], int n)
{
    unordered_set<int> SET;
    for (int i = 0; i < n; i++)
        SET.insert(arr[i]);

    int output = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr[i] - 1) == SET.end())
        {
            int temp = arr[i];

            while (SET.find(temp) != SET.end())
                temp++;

            output = max(output, temp - arr[i]);
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 24, 30, 26, 99, 25 };
    int n = sizeof(arr) / sizeof(int);
    cout << "Largest Set found : "<<getMaxConsecutiveNumber(arr, n)<< endl;
    return 0;
}
Largest Set found : 3

ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಪ್ರಸ್ತುತ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

import java.util.HashSet;

class LargestConsecutiveSet
{
    public static int getMaxConsecutiveNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
        }
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if(SET.contains(arr[i]))
            {
                int temp = arr[i];
                while (SET.contains(temp))
                    temp ++;

                output = Math.max(output, temp - arr[i]);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2, 24, 30, 26, 99, 25};
        int n = arr.length;
        System.out.println("Largest Set found : "+getMaxConsecutiveNumber(arr, n));
    }
}
Largest Set found : 3

ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಪ್ರಸ್ತುತ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಏಕೆಂದರೆ ನಾವು ಹ್ಯಾಶ್‌ಸೆಟ್ ಅನ್ನು ಬಳಸಿದ್ದೇವೆ, ಅದು ನಿರಂತರ ಸಮಯದಲ್ಲಿ ಸೇರ್ಪಡೆ, ಅಳಿಸುವಿಕೆ ಮತ್ತು ಶೋಧ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಅನುಮತಿಸುತ್ತದೆ.

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

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ನಾವು N ಅಂಶಗಳನ್ನು ಸೆಟ್ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಿದ್ದೇವೆ ಆದ್ದರಿಂದ ರೇಖೀಯ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆ.

ರೆಫರೆನ್ಸ್