Минимизирајте ја максималната разлика помеѓу височините


Ниво на тешкотија Медиум
Често прашувано во Adobe Cisco Фанатици Yandex
Низа Алчен

Изјава за проблем

Дадени ви се височини на n кули и број 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.

Toе ја сортираме низата ако нема подредена низа, ние само ја сортираме. Ние треба да решиме за минималната разлика помеѓу најголема висина и најмала висина во рамките на низата. Значи, ја поставуваме вредноста на максимумот на k повеќе од првиот елемент и минималната на k помалку од последниот елемент на низата. Овие вредности делуваат како променлива за помош и го поставуваат temp на 0. И ние ќе провериме дали минималната вредност што ја ажуриравме е поголема од максималната, затоа само ќе ја замениме

Сега ќе ја пресечеме низата до вториот последен елемент и ќе ја поставиме разликата на вредноста на тековната низа минус k (arr [i] - k) и збирот на додавањето на arr [i] и k. Toе провериме дали разликата што ја добивме сега е поголема или помала од разликата помеѓу моментално ажурираната вредност. Willе го ажурираме според дадениот услов и ќе го продолжиме сè додека не имаме помала и поголема разлика помеѓу максималниот и минимумот што го создадовме. Тогаш ние само го враќаме помалиот помеѓу разликата и максимумот-минимум. Така ја минимизираме максималната разлика помеѓу висините.

Минимизирајте ја максималната разлика помеѓу височините

Код за да се минимизира максималната разлика помеѓу проблемот со висините

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)  каде „Н“ е бројот на елементи во низата. Значи, минимизирајте ја максималната разлика помеѓу проблемот со височините и има сложеност во времето слична на таа од спои вид.

Комплексноста на просторот за минимизирање на максималната разлика помеѓу проблемот со висините

Тој)  каде „Н“ е бројот на елементи во низата. Значи, минимизирајте ја максималната разлика помеѓу проблемот со височините, има линеарна просторна комплексноста.