Максімальная адлегласць у масіве


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка Google Аракул
масіў гашыш

У задачы "Максімальная адлегласць у масіве" гаворыцца, што вам дадзена "П" няма. масіваў і ўсе масівы прыводзяцца ў парадку ўзрастання. Ваша задача знайсці максімальную розніцу / абсалютную розніцу двух лікаў у масіў і мы можам вызначыць максімальную адлегласць паміж двума лікамі як абс | ab |. Вы можаце выбраць два лікі, каб сфармаваць розныя масівы і знайсці абс | ab | як максімальная розніца.

Прыклад

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

Тлумачэнне

Паколькі лік "0" у другім масіве і лік "5" у трэцім масіве дае максімальную абсалютную розніцу ва ўсім масіве.

Алгарытм

  1. Абвясціце пераменную выхад і ўсталюйце 0.
  2. Усталюйце мінімальнае значэнне як вар[0] [0].
  3. Усталюйце значэнне максімуму вар даўжыня першага радка, г.зн. максімальны= varray [0] [0th даўжыня шэрагу-1].
  4. Знайсці максімальнае значэнне розніцы паміж першым элементам першага масіва і апошнім элементам другога масіва і розніцай паміж апошнім элементам першага масіва і першым элементам другога масіва
  5. Такім чынам, знайдзіце максімальнае значэнне паміж значэннем, атрыманым з вышэйпрыведзенага радка, і вывядзіце і захавайце яго для вываду.
  6. Знайдзіце меншае значэнне паміж варрай [i] [0] і мінімальны і ўсталяваць яго на мінімум.
  7. Знайдзіце большае значэнне паміж варрай [i] [памер_радка-1] і максімальны і ўсталюйце яго на максімум.
  8. Паўтарыце вышэйапісаны працэс да канца масіва.
  9. Зваротны выхад.

Тлумачэнне максімальнай адлегласці ў масіве

Наша задача знайсці максімальную абсалютную розніцу паміж двума лікамі ў розных масівах. Мы можам проста выкарыстаць укладзены "цыкл" і зрабіць гэта простым, выявіўшы максімальную розніцу паміж усімі лічбамі.

Але замест таго, каб выкарыстоўваць укладзеныя цыклы і абыходзіць усе элементы масіва. Мы можам выкарыстоўваць просты для цыкл і маюць эфектыўнае рашэнне. Паколькі ўсе элементы адсартаваны па ўзрастанні ва ўваходным масіве. Нам проста трэба знайсці адрозненні паміж апошнім і першым элементамі розных масіваў. Таму што толькі гэтыя два пазіцыянаваныя лікі могуць даць максімальную розніцу. У рэшце рэшт, кожны масіў сартуецца, і першы элемент заўсёды найменшы альбо мінімальны сярод іншых. І апошнім элементам будзе найбольшая колькасць масіва.

Такім чынам, давайце тут возьмем прыклад і развяжам яго:

Уваход: arr [] [] = {{0,2,4}, {2,3}, {4,5,6}};

Выхад = 0, максімум = 4, мінімум = 0, i = 1

выхад = std :: макс (выхад,

std :: max (abs (varray [i] [varray [i] .size () - 1] - мінімум),

abs (максімум-варрай [i] [0])))

Выхад захоўваецца як 3

максімум застаецца роўным 4, мінімум застаецца роўным 0, i = 2

выхад = std :: макс (выхад,

std :: max (abs (varray [i] [varray [i] .size () - 1] - мінімум),

abs (максімум-варрай [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

Праграма 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

Аналіз складанасці

Складанасць часу

Аб (п) дзе n - колькасць элементаў у масіве. Таму што мы проста перамяшчаліся па радках 2D-масіва альбо матрыцы. Але мы ніколі не перабіралі слупкі нашай матрыцы ўводу.

Касмічная складанасць

O (1) як мы выкарыстоўвалі пастаянную прастору. Так як мы выкарыстоўвалі толькі пастаянную колькасць зменных. Падыход мае пастаянную касмічную складанасць.

Спасылкі