අරා වල පවතින උපරිම අනුක්‍රමික අංක


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇසොලයිට් ඇෙබෝ ඇමේසන් ෆෝකයිට් MAQ
අරා හැෂ්

ගැටළු ප්රකාශය

ඔබට පෙළක් ඇතැයි සිතමු නිඛිල ප්‍රමාණයෙන් එන්. “අරාව තුළ පවතින උපරිම අනුක්‍රමික සංඛ්‍යා” ගැටළුව අරාවෙහි විසිරී යා හැකි අඛණ්ඩ සංඛ්‍යා ගණන සොයා ගැනීමට අසයි.

උදාහරණයක්

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

පැහැදිලි කිරීම: අඛණ්ඩ අංක ⇒ 24, 25, 26 (3 කට්ටලයක්) වේ.

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

පැහැදිලි කිරීම: අඛණ්ඩ සංඛ්‍යා numbers -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 ගණනය කිරීමෙන් වැඩි කරන්නෙමු, එබැවින් එය අඛණ්ඩ සංඛ්‍යා ද වනු ඇත.

අපි දැන් නිමැවුමේ උපරිමය සහ තාවකාලික-ආර් [i] හි වෙනස සොයා ගත යුතුව ඇත, මෙම වෙනස ගණනය කිරීම්වල වැරදි සංඛ්‍යාවක් ලබා දෙයි යැයි නොසිතන්න, මන්දයත් තාවකාලිකව වැඩිවන අගය අපට ලැබෙනු ඇත. ලූප්, අපට දැනට පවතින අනුක්‍රමික සංඛ්‍යා නිවැරදිව ලැබෙනු ඇත. එවිට අපි ප්‍රතිදානය සහ ටෙම්ප්-ආර් [i] අතර වෙනස (ප්‍රතිදානය, තාවකාලික-ආර් [i]) අතර උපරිමය ගබඩා කරමු. Arr [i] යනු අඛණ්ඩ සංඛ්‍යා මාලාවක් සඳහා ආරම්භක ලක්ෂ්‍යයක් සහ තාවකාලික, අවසන් ලක්ෂ්‍යයකි. මුළු අරාව හරහා ගමන් කරන විට උපරිම ප්‍රතිදානය සොයා ගන්නා තෙක් මෙම පියවර නැවත සිදු වේ.

අරා වල පවතින උපරිම අනුක්‍රමික අංක

ක්රියාත්මක කිරීම

අරා තුළ පවතින උපරිම අනුක්‍රමික අංක සොයා ගැනීමට C ++ වැඩසටහන

#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) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. මන්ද අපි හැෂ්සෙට් භාවිතා කර ඇති අතර එමඟින් නිරන්තර වේලාවට ඇතුළු කිරීම, මකා දැමීම සහ සෙවීමේ ක්‍රියාවලියට ඉඩ ලබා දේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. අපි N මූලද්‍රව්‍ය කට්ටලය තුළ ගබඩා කර ඇති අතර එමඟින් රේඛීය අවකාශ සංකීර්ණතාව.

විමර්ශන