陣列中的最大距離


難度級別 容易獎學金
經常問 土磚 亞馬遜 谷歌 神諭
排列 哈希

問題“數組中的最大距離”表明您已獲得 “ n” 不。 數組,所有數組均按升序排列。 您的任務是找到一個數字中兩個數字的最大差/絕對差 排列 我們可以定義兩個數字之間的最大距離為 abs | ab |。 您可以選擇兩個數字來形成不同的數組,然後找到 abs | ab | 作為最大差異。

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

解釋

因為第二個數組中的數字“ 0”和第三個數組中的數字“ 5”在整個數組中給出了最大的絕對差。

算法

  1. 聲明變量輸出並將其設置為0。
  2. 將最小值設置為 虛擬數組[0] [0]。
  3. 設置最大值 varray的 第一行長度,即 最大= varray [0] [0th 行長-1]。
  4. 求第一個數組的第一個元素與第二個數組的最後一個元素之間的差以及第一個數組的最後一個元素與第二個數組的第一個元素之間的差的最大值
  5. 因此,找到上述行產生的值與輸出之間的最大值,並將其存儲到輸出中。
  6. 查找之間的較小值 varray [i] [0]最低限度 並將其設置為最小值。
  7. 在兩者之間找到更大的價值 varray [i] [row_size-1]最大 並將其設置為最大值。
  8. 重複上述過程,直到數組結束。
  9. 返回輸出。

數組中最大距離的解釋

我們的任務是找到不同數組中兩個數字之間的最大絕對差。 我們可以簡單地使用嵌套的“ for循環”,並通過找出所有數字的最大差來簡化它。

但是不要使用嵌套循環並遍歷數組的所有元素。 我們可以用一個簡單的 循環並有一個有效的解決方案。 由於所有元素在輸入數組中均按升序排序。 我們只需要找到不同數組的最後一個元素與第一個元素之間的差異即可。 因為只有這兩個定位的數字才能給出最大的差異。 畢竟,對每個數組進行排序,並且第一個元素始終是其他元素中的最小或最小。 最後一個元素將是數組中最大的元素。

因此,讓我們在這裡舉一個例子並解決它:

輸入:arr [] [] = {{0,2,4},{2,3},{4,5,6}};

輸出= 0,最大= 4,最小= 0,i = 1

輸出= std ::最大(輸出,

std :: max(abs(varray [i] [varray [i] .size()-1] – minimum),

abs(maximum-varray [i] [0])))

輸出存儲為3

最大值保留為4,最小值保留為0,i = 2

輸出= std ::最大(輸出,

std :: max(abs(varray [i] [varray [i] .size()-1] – minimum),

abs(maximum-varray [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

複雜度分析

時間複雜度

O(N) 其中n是數組中元素的數量。 因為我們只是遍歷2D數組或矩陣的行。 但是我們從未遍歷輸入矩陣的列。

空間複雜度

O(1) 因為我們使用了恆定的空間由於我們只使用了恆定數量的變量。 該方法具有恆定的空間複雜性。

參考