מרחק מקסימאלי במערך


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית Google אורקל
מערך בליל

הבעיה "מרחק מקסימלי במערך" קובעת שניתן לך "N" לא. של מערכים וכל המערכים ניתנים בסדר עולה. המשימה שלך היא למצוא את ההפרש / ההפרש המקסימלי של שני מספרים ב- מערך ונוכל להגדיר את המרחק המרבי בין שני מספרים כ- שרירי הבטן | 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] [row_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

ניתוח מורכבות

מורכבות זמן

O (n) כאשר n הוא מספר האלמנטים במערך. כי פשוט עברנו מעל השורות של מערך דו-ממדי או מטריצה. אבל מעולם לא עברנו את העמודים של מטריצת הקלט שלנו.

מורכבות בחלל

O (1) כאשר השתמשנו במרחב קבוע. מכיוון שהשתמשנו רק במספר קבוע של משתנים. לגישה יש מורכבות חללית מתמדת.

הפניות