Максимално разстояние в масива


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка Google Оракул
Array Хашиш

Проблемът „Максимално разстояние в масива“ гласи, че сте получили "н" не. на масивите и всички масиви са дадени във възходящ ред. Вашата задача е да намерите максималната разлика / абсолютната разлика на две числа в масив и можем да определим максималното разстояние между две числа като абс | ab |. Можете да изберете две числа, за да оформите различни масиви и да намерите абс | ab | като максималната разлика.

Пример

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

Обяснение

Тъй като числото „0“ във втория масив и числото „5“ в третия масив дава максималната абсолютна разлика в целия масив.

алгоритъм

  1. Декларирайте изходна променлива и я задайте на 0.
  2. Задайте минималната стойност като варира[0] [0].
  3. Задайте стойността на максимум varray's дължина на първия ред, т.е. максимален= varray [0] [0th дължина на реда-1].
  4. Намерете максималната стойност на разликата между първия елемент на първия масив и последния елемент на втория масив и разликата между последния елемент на първия масив и първия елемент на втория масив
  5. И така, намерете максималната стойност между стойността, получена от горния ред и изведете и я съхранявайте за изход.
  6. Намерете по-малката стойност между Varray [i] [0] и минимум и го настройте на минимум.
  7. Намерете по-голямата стойност между Varray [i] [size_size-1] и максимален и го настройте на максимум.
  8. Повторете горния процес до края на масива.
  9. Връщане на изхода.

Обяснение за максимално разстояние в масива

Нашата задача е да намерим максималната абсолютна разлика между двете числа в различни масиви. Можем просто да използваме вложено „за цикъл“ и да го улесним, като открием максималната разлика на всички числа.

Но вместо да се използват вложени цикли и да се обхождат всички елементи на масива. Можем да използваме проста за цикъл и имат ефективно решение. Тъй като всички елементи са сортирани във възходящ ред във входния масив. Просто трябва да намерим разликите между последния и първия елемент на различни масиви. Защото само тези две позиционирани числа могат да дадат максималната разлика. В края на краищата всеки масив е сортиран и първият елемент винаги е най-малък или минимален сред другите. И последният елемент ще бъде най-големият брой на масива.

Така че нека вземем пример и да го разрешим:

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

Изход = 0, максимум = 4, минимум = 0, i = 1

изход = std :: max (изход,

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

абс (максимално-вариращ [i] [0])))

Изходът се съхранява като 3

максимумът остава 4, минималният остава 0, i = 2

изход = std :: max (изход,

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

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) тъй като използвахме постоянно пространство. Тъй като сме използвали само постоянен брой променливи. Подходът има постоянна космическа сложност.

Препратки