Давтагдсан дэд массивын хамгийн их урт  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Үнэндээ Karat Roblox
Array Хоёртын хайлт Динамик програмчлал Хаширч байна

"Давтагдсан дэд массивын хамгийн их урт" гэсэн дугаарт бид 1 массив ба 2 массив гэсэн XNUMX массив өгсөн тул таны даалгавар нь хоёуланд нь гарч ирэх дэд массивын хамгийн их уртыг олох явдал юм. массивууд.

Жишээ нь  

Орц:

[1,2,3,2,1]
[3,2,1,4,7]

Үр дүн:

3

Тайлбар:

Учир нь дэд массивын хамгийн их урт нь 3, нийтлэг массив нь [3,2,1]

Давтагдсан дэд массивын хамгийн их уртPin

Алгоритм  

  1. Гаралтыг 0 болгож тохируулна уу.
  2. Бодит оролтын массивын уртаас 1-ээс их урттай хувьсагчийн бүхэл массивыг зарлах.
  3. -С эхлэн массивын сүүлийн индекс массив1 [i] массив2 [j] -тай тэнцүү байгаа эсэхийг шалгана уу, хэрэв үнэн бол val [i] [j] = val [i + 1] [j + 1] +1 болно.
  4. Гаралт val [i] [j] -ээс бага эсэхийг шалгаад гаралт = val [i] [j] -г хий.
  5. Бүх массивыг давтаж, нөхцлийг шалгахдаа бид хамгийн их гаралтыг авна.
  6. Гаралтыг буцаах.

Тайлбар  

Бүтээгдэхүүнээ олж авахын тулд бид энгийн дамжуулалт хийх хэрэгтэй. Үүний тулд бид гаралтыг 0 гэж эхлүүлэх гэж байна. Дараа нь бид 2-D гэж зарлах болно Матриц массив1 ба массив2-ийн уртаас нэг урт илүү.

Бид массивын сүүлийн индексээс массивыг хоёуланг нь туулах болно. Тиймээс бид зарим нөхцлийг шалгаж, үр дүнг гаралтад хадгалах болно.

Тиймээс нэг жишээ аваад цааш үргэлжлүүлье.

Жишээ нь

Массив дараах байдлаар байна гэж үзье.

мөн үзнэ үү
Гурван стекийн хамгийн дээд нийлбэрийг олох

int массив1 [] = {1,2,3,2,1};

int массив2 [] = {3,2,1,4,7};

гаралт = 0;

  • i = 4, j = 4;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

гаралт = 0;

  • i = 4, j = 3;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

гаралт = 0;

  • i = 4, j = 2;

хэрэв массив1 [i] == массив2 [j] үнэнийг буцааж, val [i] [j] = val [i + 1] [j + 1] +1

then val[4][2]=val[5][3]+1=1 then val[i][j]=1.

дараа нь <val [i] [j] гаралт үнэн болж, гаралт = 1 байх эсэхийг шалгана уу.

гаралт = 1;

  • i = 4, j = 1;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 4, j = 0;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 3, j = 4;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 3, j = 3;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 3, j = 2;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 3, j = 1;

хэрэв массив1 [i] == массив2 [j] үнэнийг буцааж, val [i] [j] = val [i + 1] [j + 1] +1

дараа нь val [3] [1] = val [4] [2] + 1 = 2 дараа нь val [3] [1] = 2.

дараа нь <val [i] [j] гаралт үнэн болж, гаралт = val [i] [j] байгаа эсэхийг шалгана уу.

гаралт = 2;

  • i = 3, j = 0;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 2, j = 4;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 2, j = 3;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 2, j = 2;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 2, j = 1;

Хэрэв массив1 [i] == array2 [j] нь худал утгыг буцааж өгөх бөгөөд юу ч хийхгүй.

  • i = 2, j = 0;

хэрэв массив1 [i] == массив2 [j] үнэнийг буцааж, val [i] [j] = val [i + 1] [j + 1] +1

дараа нь val [2] [0] = val [3] [1] + 1 = 2 + 1 дараа нь val [2] [0] = 3.

дараа нь <val [i] [j] гаралт үнэн болж, гаралт = val [2] [0] байгаа эсэхийг шалгана уу.

гаралт = 3;

Энэ нь давтах массивын хамгийн их урт байх болно, гэхдээ бид элементүүдийг дайрч өнгөрөхөд тэнцүү байгааг олж мэдсэн ч энэ нь гаралтад шинэчлэлт хийхгүй, учир нь энэ нь дэд мөр биш байх болно.

i = 1, j = 1 үед бид дараагийн ижил төстэй элементийг олох болно, ингэснээр val [1] [1] = val [2] [2] +1;

мөн үзнэ үү
Дарааллыг нэмэгдүүлэхийн тулд хамгийн бага своп хийх

хэрэв бид <val [1] [1] гаралтыг шалгаж байвал худал утга гарах бүрт юу ч хийхгүй болно.

Тэгэхээр энд гаралт 3 байна.

Хэрэгжүүлэх  

Давтагдсан дэд массивын хамгийн их уртад зориулсан C ++ програм

#include <iostream>
using namespace std;

int lengthOfRepeatedArray(int array1[], int array2[])
{
    int output = 0;
    int val[6][6]= {0};

    for (int i = 4; i >= 0; --i)
    {
        for (int j = 4; j >= 0; --j)
        {
            if (array1[i] == array2[j])
            {
                val[i][j] = val[i+1][j+1] + 1;
                if(output < val[i][j])
                {
                    output = val[i][j];
                }
            }
        }
    }
    return output;
}
int main()
{
    int a[]= {1,2,3,2,1};
    int b[]= {3,2,1,4,7};

    cout<<lengthOfRepeatedArray(a,b);
    return 0;
}
3

Давтагдсан дэд массивын хамгийн их уртад зориулсан Java програм

class repeatedArrayLength
{
    public static int lengthOfRepeatedArray(int[] array1, int[] array2)
    {
        int output = 0;
        int val[][] = new int[array1.length + 1][array2.length + 1];
        for (int i = array1.length - 1; i >= 0; --i)
        {
            for (int j = array2.length - 1; j >= 0; --j)
            {
                if (array1[i] == array2[j])
                {
                    val[i][j] = val[i+1][j+1] + 1;
                    if(output < val[i][j])
                        output = val[i][j];
                }
            }
        }
        return output;
    }
    public static void main(String []args)
    {
        int a[]= {1,2,3,2,1};
        int b[]= {3,2,1,4,7};
        System.out.println(lengthOfRepeatedArray(a,b));
    }
}
3

Давтагдсан дэд массивын хамгийн их уртыг тодорхойлох нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (a × b) хаана А нь эхний массивын хэмжээ ба “Б” нь хоёр дахь массивын хэмжээ юм.

Сансрын нарийн төвөгтэй байдал

O (a × b) хаана А нь эхний массивын хэмжээ ба “Б” нь хоёр дахь массивын хэмжээ юм.

лавлагаа