צמצם את ההפרש המקסימלי בין הגבהים


רמת קושי בינוני
נשאל לעתים קרובות Adobe סיסקו קנאות Yandex
מערך חמדן

הצהרת בעיה

מקבלים כמה גבהים של מגדלים ומספר k. אנחנו יכולים להגדיל את גובה המגדל ב- k או להקטין את הגובה ב- k, אבל רק בפעם אחת. הצהרת הבעיה מבקשת למזער את ההפרש המרבי בין הגבהים. כלומר לברר את ההבדל המינימלי בין גבהי המגדלים (הגובה הארוך ביותר - הגובה הקטן ביותר) לאחר השינוי שביצענו.

דוגמה

arr[] = {7,12,3}

k=8
9

הסבר: שנה 7 עד 15, 12 עד 20 ו- 3 עד 11 ההפרש המרבי יהיה 9 ולא יכול להיות נמוך מזה.

 

arr[] = {1,5,15,10}

k=3
8

הסבר: מערך שונה ששונה הוא arr [] = {4,8,12,7}. ההבדל המרבי יהיה 8.

 

אלגוריתם כדי למזער את ההפרש המרבי בין הגבהים

1. Sort the given array.
2. Set the diff to the difference between the least element of the array and the first element of an array.
3. Set minimum to the first element of array + k and maximum to last element - k of the array.
4. Traverse the array from i=1 to i<n-1(one less than the length of the array).
  1. Set difference to arr[i]-k.
  2. Set sum to arr[i]+k.
  3. Check if the difference is greater than equal to minimum or sum is less than or equal to maximum.
    1. If true, then continue and skip this traversal.
  4. Check if maximum-difference is less than or equal to sum-minimum.
    1. If true, then update minimum to difference.
  5. Else set the maximum to sum.
5. Return the minimum between the diff and maximum-minimum.

 

הסבר

נתנו גובה של n מגדלים. עלינו למצוא למזער את ההפרש המרבי בין הגבהים. כדי שנוכל לעשות את שניהם כאן ולבדוק את אחד המתאים. אבל לפני כן, עלינו להגדיר כמה תנאים כמו גם אם אורכו של מערך הוא 1, כך שלא ניתן לחשב את ההפרש המינימלי מכיוון שיש רק ערך אחד במערך נתון, אז אנחנו פשוט מחזירים 0.

אנחנו הולכים למיין את המערך אם אין מערך ממוין, אנחנו פשוט ממיינים אותו. עלינו לפתור את ההבדל המינימלי בין ה- הגובה הגדול ביותר והגובה הקטן ביותר בתוך מערך. אז קבענו את הערך המקסימלי ל- k יותר מהאלמנט הראשון ולמינימום ל- k פחות מהאלמנט האחרון במערך. ערכים אלה משמשים עבורנו כמשתנה מסייע ומגדירים את temp ל- 0. ונבדוק אם הערך המינימלי שזה עתה עדכנו גדול מהמקסימום, לכן פשוט נחליף אותו.

כעת נחצה את המערך עד האלמנט השני האחרון ונקבע את ההפרש לערך המערך הנוכחי מינוס k (arr [i] - k) ונסכם לתוספת arr [i] ו- k. אנו נבדוק אם ההבדל שאנו מקבלים כעת גדול או קטן מההפרש בין הערך המעודכן כעת. אנו נעדכן אותו על פי התנאי הנתון ונמשיך בכך עד שיהיה לנו ההבדל הקטן והגדול יותר בין המקסימום למינימום שיצרנו. ואז אנחנו רק מחזירים את הקטן יותר בין ההבדל למקסימום-מינימום. כך אנו ממזערים את ההפרש המרבי בין הגבהים.

צמצם את ההפרש המקסימלי בין הגבהים

קוד למזעור ההפרש המקסימלי בין בעיית הגבהים

קוד C ++

#include<iostream>
#include<algorithm>

using namespace std;

int getMinimizeHeights(int arr[], int n, int k)
{
    if (n == 1)
        return 0;

    sort(arr, arr+n);

    int diff = arr[n-1] - arr[0];

    int minimum = arr[0] + k;
    int maximum = arr[n-1] - k;
    int temp = 0;

    if (minimum > maximum)
    {
        temp = minimum;
        minimum = maximum;
        maximum = temp;
    }
    for (int i = 1; i < n-1; i ++)
    {
        int difference = arr[i] - k;
        int sum = arr[i] + k;
        if (difference >= minimum || sum <= maximum)
            continue;

        if (maximum - difference <= sum - minimum)
            minimum = difference;
        else
            maximum = sum;
    }
    return min(diff, maximum - minimum);
}
int main()
{
    int arr[] = {7,12,3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 8;
    cout << getMinimizeHeights(arr, n, k);
    return 0;
}
9

 

קוד Java

import java.util.*;
import java.lang.*;
import java.io.*;
 
class MinimizeHeights
{
    public static int getMinimizeHeights(int arr[], int n, int k)
    {
        if (n == 1)
            return 0;
        Arrays.sort(arr);
        int diff = arr[n-1] - arr[0];
        int minimum = arr[0] + k;
        int maximum = arr[n-1] - k;
        int temp = 0;
        if (minimum > maximum)
        {
            temp = minimum;
            minimum = maximum;
            maximum = temp;
        }
        for (int i = 1; i < n-1; i ++)
        {
            int difference = arr[i] - k;
            int sum = arr[i] + k;
            if (difference >= minimum || sum <= maximum)
                continue;
            if (maximum - difference <= sum - minimum)
                minimum = difference;
            else
                maximum = sum;
        }
        return Math.min(diff, maximum - minimum);
    }
    public static void main(String[] args)
    {
        int arr[] = {7, 12, 3};
        int n = arr.length;
        int k = 8;
        System.out.println(getMinimizeHeights(arr, n, k));
    }
}

 

9

 

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

מורכבות זמן למזעור ההפרש המרבי בין בעיית הגבהים

O (n יומן n)  איפה "N" הוא מספר האלמנטים במערך. אז למזער את ההבדל המרבי בין בעיית הגבהים יש מורכבות זמן דומה לזו של מיזוג מיון.

מורכבות שטח למזער את ההבדל המרבי בין בעיית הגבהים

O (n)  איפה "N" הוא מספר האלמנטים במערך. אז למזער את ההבדל המרבי בין בעיית הגבהים יש מורכבות שטח ליניארית.