Максимално растојание по низа


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Google Oracle
Низа Хаш

Проблемот „Максимално растојание по низа“ наведува дека ви е даден „Н“ не на низите и сите низи се дадени во растечки редослед. Ваша задача е да пронајдете максимална разлика / апсолутна разлика на два броја во низа и можеме да го дефинираме максималното растојание помеѓу два броја како апс | аб |. Можете да изберете два броја за да формирате различни низи и да ја пронајдете апс | аб | како максимална разлика.

пример

[  [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. Враќање на излез.

Објаснување за максималното растојание во низата

Нашата задача е да најдеме максимална апсолутна разлика помеѓу двата броја во различни низи. Едноставно можеме да користиме вгнездени „за јамка“ и да го олесниме со тоа што ќе ја откриеме максималната разлика на сите броеви.

Но, наместо да користите вгнездени јамки и да ги прелистувате сите елементи на низата. Можеме да користиме едноставна за јамка и имаат ефикасно решение. Бидејќи сите елементи се подредени во растечки редослед во влезната низа. Треба само да ги најдеме разликите помеѓу последните и првите елементи на различните низи. Бидејќи само овие два позиционирани броја можат да дадат максимална разлика. На крајот на краиштата, секоја низа е подредена и првиот елемент е секогаш најмал или минимум меѓу другите. И последниот елемент ќе биде најголемиот број на низата.

Па, дозволете ни да земеме пример и да го решиме:

Внесување: arr [] [] = {{0,2,4}, {2,3}, {4,5,6}};

Излез = 0, максимум = 4, минимум = 0, i = 1

излез = std :: макс (излез,

std :: max (апс (апсорпција [i] [varray [i]. големина () - 1] - минимум)

апс (максимум-варијат [i] [0])))

Излезот се чува како 3

максимумот останува како што е 4, минимумот останува како што е 0, i = 2

излез = std :: макс (излез,

std :: max (апс (апсорпција [i] [varray [i]. големина () - 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

Јава програма за максимално растојание во низа

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 низа или матрица. Но, ние никогаш не ги прелистувавме колоните од нашата влезна матрица.

Комплексноста на просторот

О (1) како што користевме постојан простор. Бидејќи користевме само постојан број на променливи. Пристапот има постојана вселенска сложеност.

Референци