អារេពិសេសជាមួយ X ដែលមានទំហំធំជាងឬស្មើ X។


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន google
អារេ ហាសហាស។

នៅក្នុងបញ្ហា“ អារេពិសេសជាមួយធាតុ X ធំជាងឬស្មើ X” យើងត្រូវបានផ្តល់ឱ្យ អារេ នៃចំនួនគត់មិនអវិជ្ជមាន។ យើងត្រូវរកលេខគត់ X ខ្លះដែលមានធាតុ X ច្បាស់ជាងឬស្មើវាក្នុងអារេ។ ប្រសិនបើមិនមានលទ្ធភាព X ដែលអាចបំពេញលក្ខខណ្ឌនេះបានទេយើងចាំបាច់ត្រូវចេញលទ្ធផល -1 ។

ឧទាហរណ៍

1 2 3 4
-1
1 3 4 5
3

វិធីសាស្រ្ត (កម្លាំងដុសខាត់)

វាប្រាកដថាប្រសិនបើមានដំណោះស្រាយ X បន្ទាប់មក X នឹងតែងតែមានតែមួយគត់។

ភស្តុតាង៖

ពិចារណាថាមានដំណោះស្រាយពីរ X និង Y ដែល X! = Y. អនុញ្ញាតឱ្យសន្មត X <អ៊ី។ ឥឡូវចំនួនធាតុធំជាងឬស្មើ X គួរតែជា X ព្រោះយើងគិតថាវាជាដំណោះស្រាយ។ ប៉ុន្តែចាប់តាំងពី Y> X មានធាតុ Y ធំជាងឬស្មើ X ដែល X! = Y ដូច្នេះការសន្មតរបស់យើងថា X ជាដំណោះស្រាយគឺខុសទេលើកលែងតែ X និង Y ស្មើ។

ដូច្នេះវាតែងតែមានដំណោះស្រាយប្លែកមួយប្រសិនបើមានដំណោះស្រាយ។ ឥឡូវវាក៏អាចសន្និដ្ឋានបានថាប្រសិនបើ X ជាដំណោះស្រាយបន្ទាប់មកចំនួនធាតុធំជាង / ស្មើនឹងវា = X ដែលគួរតែតិចជាង N ដែល N = ទំហំអារេ (ជាចំនួនអតិបរមានៃធាតុដែលអាចធ្វើបាន) = N) ។

ដូច្នេះប្រសិនបើមានដំណោះស្រាយ X មានបន្ទាប់មកវា ត្រូវតែកុហកនៅក្នុងជួរ [1, អិន] ។

យើងអាចពិនិត្យមើលរាល់ចំនួនគត់នៅក្នុងជួរ [1, អិន] ប្រសិនបើចំនួនធាតុនៅក្នុងអារេធំជាងឬស្មើទៅនឹងចំនួនគត់ណាមួយនៅក្នុងជួរគឺស្មើនឹងចំនួនគត់នោះ។ ឧទាហរណ៍ពិចារណាអារេ = {១, ៣, ៤, ៥} ។ ឥឡូវ ១ និង ២ មានធាតុ ៤ និង ៣ ធំជាងឬស្មើនឹងពួកវាក្នុងអារេរៀង។ ចំនួនធាតុធំជាង / ស្មើ ៣ = ៣ ។ ដូច្នេះ ៣ គឺជាដំណោះស្រាយតែមួយគត់។ ដោយសារយើងឆ្លងកាត់មែកធាងទាំងមូលដើម្បីរកចំនួនធាតុធំជាងចំនួនគត់ទាំងអស់នៅក្នុងជួរ៖ [១, អិន] វិធីនេះយឺត។

ក្បួនដោះស្រាយ

  1. ដំណើរការរង្វិលជុំពី i = 1 ដល់ i = N ដើម្បីពិនិត្យរកដំណោះស្រាយ៖
    • រាប់ចំនួនធាតុធំជាងឬស្មើ 'i'នៅក្នុងអារេ
      • ប្រសិនបើការរាប់ស្មើនឹង 'i'ត្រឡប់មកវិញខ្ញុំ
  2. ត្រឡប់ទៅវិញ -1;

ការអនុវត្តអារេពិសេសជាមួយ X សមាសធាតុធំជាងឬដំណោះស្រាយ X Leetcode

កម្មវិធី C ++

#include <bits/stdc++.h>
using namespace std;

int specialArray(vector <int> &a)
{
    int n = a.size() , counter = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        counter = 0;
        for(int j = 0 ; j < n ; j++)
            if(a[j] >= i)
                counter++;
        if(counter == i)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

កម្មវិធីចាវ៉ា

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length , counter = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            counter = 0;
            for(int j = 0 ; j < n ; j++)
                if(a[j] >= i)
                    counter++;
            if(counter == i)
                return i;
        }
        return -1;
    }
}
3

ការវិភាគស្មុគស្មាញនៃអារេពិសេសជាមួយ X ធាតុធំជាងឬដំណោះស្រាយ X Leetcode ដែលមានតំលៃស្មើ

ស្មុគស្មាញពេលវេលា

O (N * N), N = ទំហំនៃអារេ។ ក្នុងករណីអាក្រក់បំផុតនៅពេល X = N គឺជាដំណោះស្រាយយើងធ្វើការប្រៀបធៀប O (N * N) ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១)។ មានតែកន្លែងចងចាំថេរប៉ុណ្ណោះដែលត្រូវបានប្រើ។

វិធីសាស្រ្ត (ប្រសើរបំផុត)

យើងអាចរក្សាទុកចំនួននៃការកើតឡើងនៃធាតុទាំងអស់នៅក្នុងតារាងដោយប្រើអារេ។ ចំណាំថាសម្រាប់ធាតុណាដែលមានតំលៃធំជាង N យើងអាចរាប់វាថាជាការកើតឡើងនៃធាតុដែលមានតំលៃ N ពីព្រោះតំលៃអតិបរមានៃដំណោះស្រាយអាចជា N ។

ឥឡូវប្រេកង់នៃធាតុធំជាងឬស្មើ X = ប្រេកង់ X + ប្រេកង់នៃធាតុទាំងអស់ធំជាង X។ ដើម្បីរកវាសម្រាប់រាល់ធាតុក្នុងជួរ [១, អិន] យើងត្រូវមានអារេប្រេកង់បច្ច័យ ។

ដូច្នេះសម្រាប់រាល់ចំនួនគត់នៅក្នុងអារេយើងត្រូវកំណត់ ប្រេកង់ [i] = ប្រេកង់ [i] + ប្រេកង់ [i + 1]សម្រាប់រាល់ 'i'នៅក្នុងជួរ [N - 1, 1] ដែលនឹងបង្កើតអារេប្រេកង់បច្ច័យទុកចំនួនធាតុធំជាងឬស្មើ "i"  as ប្រេកង់ [i] ។

ឥឡូវនេះដោយសារតែតារាងមើលយើងអាចពិនិត្យរកដំណោះស្រាយសម្រាប់ចំនួនគត់ណាមួយនៅក្នុងជួរ [1, N] នៅក្នុង ឱ (១) ពេលវេលា។ នេះជាករណីដែលយើង ពាណិជ្ជ​កម្ម​បិទ ការចងចាំដើម្បីធ្វើឱ្យទាន់ពេលវេលា។ ដោយសារតារាងមានទំហំ N យើងមិនមានការព្រួយបារម្ភអំពីដែនកំណត់នៃការចងចាំផងដែរ។

 

អារេពិសេសជាមួយ X ដែលមានទំហំធំជាងឬស្មើ X។

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមក ប្រេកង់ អារេនៃទំហំ N, មានតម្លៃដូចគ្នា សូន្យ
  2. សម្រាប់ធាតុទាំងអស់ i  នៅក្នុងអារេ:
    1. If i > N, ប្រេកង់បង្កើន [N]
    2. ប្រេកង់បង្កើន [i]
  3. បង្កើតអារេផលបូកបច្ច័យពី ប្រេកង់ ជា:
    1. សម្រាប់រាល់ធាតុចាប់ពី i = អិន - ១ ទៅ i = 0
      1. សំណុំ ប្រេកង់ [i] = ប្រេកង់ [i] + ប្រេកង់ [i +1]
  4. ដំណើរការរង្វិលជុំពី i = ១ ដល់ i = ន
    1. If i == ប្រេកង់ [i], ត្រឡប់មកវិញ i
  5. ត្រឡប់ -1

ការអនុវត្តអារេពិសេសជាមួយ X សមាសធាតុធំជាងឬដំណោះស្រាយ X Leetcode

កម្មវិធី C ++

#include <bits/stdc++.h>
using namespace std;

int specialArray(vector<int>& a)
{
    int n = a.size();
    vector <int> frequency(n + 1 , 0);
    for(int i = 0 ; i < n ; i++)
        if(a[i] > n)
            frequency[n]++;
        else
            frequency[a[i]]++;

    for(int i = n - 1 ; i >= 0 ; i--)
        frequency[i] += frequency[i + 1];

    for(int i = 0 ; i <= n ; i++)
        if(frequency[i] == i)
            return i;

    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

កម្មវិធីចាវ៉ា

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length;
        int[] frequency = new int[n + 1];
        for(int i = 0 ; i < n ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < n ; i++)
            if(a[i] > n)
                frequency[n]++;
            else
                frequency[a[i]]++;

        for(int i = n - 1 ; i >= 0 ; i--)
            frequency[i] += frequency[i + 1];

        for(int i = 0 ; i <= n ; i++)
            if(frequency[i] == i)
                return i;

        return -1;
    }
}
3

ការវិភាគស្មុគស្មាញនៃអារេពិសេសជាមួយ X ធាតុធំជាងឬដំណោះស្រាយ X Leetcode ដែលមានតំលៃស្មើ

ស្មុគស្មាញពេលវេលា

O (N), N = ទំហំនៃអារេ។ យើងអាចពិនិត្យរកចំនួនគត់ណាមួយនៅក្នុងម៉ោង O (១) ដូច្នេះក្នុងករណីដែលអាក្រក់បំផុតយើងប្រើពេលវេលា (N) ។

ភាពស្មុគស្មាញនៃលំហ

O (N)។ ទំហំអង្គចងចាំលីនេអ៊ែរត្រូវបានប្រើសម្រាប់រក្សាទុកប្រេកង់។