Առավելագույն հեռավորությունը զանգվածում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon Google Պատգամախոս
Դասավորություն Խանգարել

«Rayանգվածի առավելագույն հեռավորությունը» խնդիրը նշում է, որ ձեզ տրված է «Ն» ոչ զանգվածների և բոլոր զանգվածները տրված են աճման կարգով: Ձեր խնդիրն է գտնել երկու թվերի առավելագույն տարբերություն / բացարձակ տարբերություն դասավորություն և մենք կարող ենք սահմանել առավելագույն հեռավորությունը երկու թվերի միջև որպես abs | ab |, Կարող եք ընտրել երկու թվեր `տարբեր զանգվածներ կազմելու և գտնելու համար abs | ab | որպես առավելագույն տարբերություն:

Օրինակ

[  [1,2,3],
[0,2,3],
[1,4,5] ]
5

բացատրություն

Քանի որ երկրորդ զանգվածում «0» թիվը և երրորդ զանգվածում «5» թիվը տալիս են առավելագույն բացարձակ տարբերությունը ամբողջ զանգվածում:

Ալգորիթմ

  1. Հայտարարել փոփոխական ելք և սահմանել 0:
  2. Սահմանեք նվազագույնի արժեքը որպես խայտաբղետ[0] [0]
  3. Սահմանեք առավելագույնի արժեքը խայտաբղետ առաջին շարքի երկարությունը, այսինքն, առավելագույնը= երանգ [0] [0th շարքի երկարություն -1]:
  4. Գտեք առաջին զանգվածի առաջին զանգվածի և երկրորդ զանգվածի վերջին տարրի և առաջին զանգվածի երկրորդ մասի և երկրորդ զանգվածի առաջին տարրի տարբերության առավելագույն արժեքը
  5. Այսպիսով, գտեք վերը նշված տողից ստացված արժեքի և ելքի առավելագույն արժեքը և պահեք այն արդյունքի համար:
  6. Գտեք ավելի փոքր արժեքը միջեւ խայտաբղետ [i] [0] և նվազագույն և սահմանել այն նվազագույնի:
  7. Գտեք ավելի մեծ արժեք միջեւ varray [i] [row_size-1] և առավելագույնը և դրեք այն առավելագույնին:
  8. Կրկնեք վերը նշված գործընթացը մինչ զանգվածի ավարտը:
  9. Վերադարձի արդյունքը:

Rayանգվածի առավելագույն հեռավորության բացատրությունը

Մեր խնդիրն է գտնել տարբեր զանգվածների երկու թվերի առավելագույն բացարձակ տարբերությունը: Մենք կարող ենք պարզապես օգտագործել տեղադրված «օղակի համար» և հեշտացնել այն ՝ պարզելով բոլոր թվերի առավելագույն տարբերությունը:

Բայց տեղադրված օղակներ օգտագործելու և զանգվածի բոլոր տարրերը հատելու փոխարեն: Մենք կարող ենք օգտագործել մի պարզ մեկը համար օղակ և ունենալ արդյունավետ լուծում: Քանի որ բոլոր տարրերը տեսակավորված են աճման կարգով մուտքային զանգվածում: Պարզապես պետք է գտնել տարբերությունները տարբեր զանգվածների վերջին և առաջին տարրերի միջև: Քանի որ միայն այս երկու դիրքավորված համարները կարող են առավելագույն տարբերություն տալ: Ի վերջո, յուրաքանչյուր զանգված տեսակավորված է, և առաջին տարրը միշտ էլ նվազագույնն է կամ նվազագույնը: Եվ վերջին տարրը կլինի զանգվածի ամենամեծ թիվը:

Այսպիսով, եկեք այստեղ օրինակ վերցնենք և լուծենք այն.

Ներածում ՝ arr [] [] = {{0,2,4}, {2,3}, {4,5,6}};

Արդյունք = 0, առավելագույն = 4, նվազագույն = 0, i = 1

ելք = std :: առավելագույն (ելք,

std :: max (abs (varray [i] [varray [i] .size () - 1] - նվազագույն),

աբս (առավելագույն տատանում [i] [0]))))

Արդյունքը պահվում է որպես 3

առավելագույնը մնում է 4-ով, նվազագույնը մնում է 0-ով, i = 2

ելք = std :: առավելագույն (ելք,

std :: max (abs (varray [i] [varray [i] .size () - 1] - նվազագույն),

աբս (առավելագույն տատանում [i] [0]))))

տարբեր զանգվածների վերջին և առաջին տարրի տարբերությունները

0-ը և 6-ը, և որից 6-ը առավելագույն տարբերությունն է, այնպես որ ելքը կդառնա 6

Եվ վերադարձիր 6:

Առավելագույն հեռավորությունը զանգվածում

C ++ ծրագիր զանգվածում առավելագույն հեռավորության համար

#include <iostream>
#include<vector>
#include<cstdlib>
using namespace std;
int getMaxDistance(vector<vector <int>> varray)
{
    int output=0;
    int minimum=varray[0][0];
    int maximum=varray[0][varray[0].size()-1];

    for(int i = 1 ; i < varray.size() ; i++ )
    {
        output=std::max(output, std::max( abs( varray[i][varray[i].size()-1] - minimum ), abs(maximum-varray[i][0]) ) );
        minimum=std::min( minimum, varray[i][0] );
        maximum=std::max( maximum, varray[i][varray[i].size()-1]);
    }
    return output;

}
int main()
{
    vector<vector<int>> vec= {{0,2,4},{2,3,4},{4,5,6}};
    cout<<"Maximum distance is:"<<getMaxDistance(vec);
    return 0;
}
Maximum distance is: 6

Programանգվածի առավելագույն հեռավորության համար Java ծրագիր

import java.util.*;
import java.io.*;

class maximumDistance
{
    public static int getMaxDistance(int array[][])
    {
        int output=0;
        int minimum=array[0][0];
        int maximum=array[0][array[0].length-1];

        for(int i = 1 ; i < array.length ; i++ )
        {
            output=Math.max(output, Math.max(Math.abs( array[i][array[i].length-1] - minimum ), Math.abs(maximum-array[i][0]) ) );
            minimum=Math.min( minimum, array[i][0] );
            maximum=Math.max( maximum, array[i][array[i].length-1]);
        }
        return output;

    }
    public static void main(String args[])
    {
        int arr[][]= {{0,2,4},{2,3},{4,5,6}};
        System.out.println("Maximum distance is:"+(getMaxDistance(arr)));
    }
}
Maximum distance is: 6

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ n - զանգվածի տարրերի քանակը: Քանի որ մենք պարզապես անցնում էինք 2D զանգվածի կամ մատրիցի տողերի վրայով: Բայց մենք երբեք չենք անցել մեր մուտքային մատրիցայի սյունակները:

Տիեզերական բարդություն

Ո (1) քանի որ մենք օգտագործում էինք անընդհատ տարածություն: Քանի որ մենք օգտագործել ենք փոփոխականների միայն հաստատուն քանակ: Մոտեցումն ունի անընդհատ տիեզերական բարդություն:

Սայլակ