Минимизировать максимальную разницу между соседними элементами в массиве

Опубликовано: 7 Января, 2022

Учитывая неубывающий массив arr [] и целое число K , задача состоит в том, чтобы удалить K элементов из массива так, чтобы максимальная разница между соседними элементами была минимальной.
Примечание: K <N - 2

Примеры:

Input: arr[] = {3, 7, 8, 10, 14}, K = 2 
Output: 2 
Explanation: 
After removing elements A[0] and A[4], 
The maximum difference between adjacent elements is minimum. 
After removing elements, the remaining array is [7, 8, 10] 

Input: arr[] = [12, 16, 22, 31, 31, 38], K = 3 
Output: 6 
Explanation: 
After removing elements A[3], A[4] and A[5], 
The maximum difference between adjacent elements is minimum. 
After removing elements, the remaining array is [12, 16, 22] 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Метод 1: Грубая сила Идея состоит в том, чтобы сгенерировать подмножества массива размером N - K, а также вычислить максимальную разницу между соседними элементами в каждой подпоследовательности. Наконец, найдите минимум таких максимальных различий.

Below is the implementation of the above approach:

C++

// C++ implementation to find the
// minimum of the maximum difference
// of the adjacent elements after
// removing K elements from the array
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the minimum
// of the maximum difference of the
// adjacent elements after removing
// K elements from the array
int minimumAdjacentDifference(int a[],
                        int n, int k)
{
    // Intialising the
    // minimum difference
    int minDiff = INT_MAX;
 
    // Traversing over subsets
    // in iterative manner
    for (int i = 0; i < (1 << n); i++) {
         
        // Number of elements to
        // be taken in the subset
        // ON bits of i represent
        // elements not to be removed
        int cnt = __builtin_popcount(i);
 
        // If the removed
        // set is of size k
        if (cnt == n - k) {
             
            // Creating the new array
            // after removing elements
            vector<int> temp;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0)
                    temp.push_back(a[j]);
            }
            // Maximum difference of adjacent
            // elements of remaining array
            int maxDiff = INT_MIN;
            for (int j = 0; j < temp.size() - 1; j++) {
                maxDiff = max(maxDiff,
                   temp[j + 1] - temp[j]);
            }
            minDiff = min(minDiff, maxDiff);
        }
    }
    return minDiff;
}
 
// Driver Code
int main()
{
    int n = 5;
    int k = 2;
 
    int a[n] = { 3, 7, 8, 10, 14 };
 
    cout << minimumAdjacentDifference(a, n, k);
    return 0;
}

Java

// Java implementation to find the
// minimum of the maximum difference
// of the adjacent elements after
// removing K elements from the array
import java.util.*;
 
class GFG{
 
    // Function to find the minimum
    // of the maximum difference of the
    // adjacent elements after removing
    // K elements from the array
    static int minimumAdjacentDifference(int a[],
                            int n, int k)
    {
        // Intialising the
        // minimum difference
        int minDiff = Integer.MAX_VALUE;
     
        // Traversing over subsets
        // in iterative manner
        for (int i = 0; i < (1 << n); i++) {
             
            // Number of elements to
            // be taken in the subset
            // ON bits of i represent
            // elements not to be removed
            int cnt = Integer.bitCount(i);
     
            // If the removed
            // set is of size k
            if (cnt == n - k) {
                 
                // Creating the new array
                // after removing elements
                 Vector<Integer> temp = new Vector<Integer>();
                for (int j = 0; j < n; j++) {
                    if ((i & (1 << j)) != 0)
                        temp.add(a[j]);
                }
 
                // Maximum difference of adjacent
                // elements of remaining array
                int maxDiff = Integer.MIN_VALUE;
                for (int j = 0; j < temp.size() - 1; j++) {
                    maxDiff = Math.max(maxDiff,
                    temp.get(j + 1) - temp.get(j));
                }
                minDiff = Math.min(minDiff, maxDiff);
            }
        }
        return minDiff;
    }
     
    // Driver Code
    public static void main(String args[])
    {
        int n = 5;
        int k = 2;
     
        int a[] = { 3, 7, 8, 10, 14 };
     
        System.out.println(minimumAdjacentDifference(a, n, k));
    }
}
 
 
// This code is contributed by AbhiThakur

Python3

# Python3 implementation to find the
# minimum of the maximum difference
# of the adjacent elements after
# removing K elements from the array
import sys
 
INT_MAX = sys.maxsize;
INT_MIN = -(sys.maxsize - 1)
 
# Function to find the minimum
# of the maximum difference of the
# adjacent elements after removing
# K elements from the array
def minimumAdjacentDifference(a, n, k) :
 
    # Intialising the
    # minimum difference
    minDiff = INT_MAX;
 
    # Traversing over subsets
    # in iterative manner
    for i in range( 1<<n) :
         
        # Number of elements to
        # be taken in the subset
        # ON bits of i represent
        # elements not to be removed
        cnt = bin(i).count("1");
 
        # If the removed
        # set is of size k
        if (cnt == n - k) :
             
            # Creating the new array
            # after removing elements
            temp = [];
            for j in range(n) :
                if ((i & (1 << j)) != 0) :
                    temp.append(a[j]);
             
            # Maximum difference of adjacent
            # elements of remaining array
            maxDiff = INT_MIN;
             
            for j in range(len(temp) - 1) :
                maxDiff = max(maxDiff, temp[j + 1] - temp[j]);
           
            minDiff = min(minDiff, maxDiff);
      
    return minDiff;
 
# Driver Code
if __name__ == "__main__" :
 
    n = 5;
    k = 2;
 
    a = [ 3, 7, 8, 10, 14 ];
 
    print(minimumAdjacentDifference(a, n, k));
   
# This code is contributed by AnkitRai01

C#

// C# implementation to find the
// minimum of the maximum difference
// of the adjacent elements after
// removing K elements from the array
using System;
using System.Collections.Generic;
 
class GFG{
  
    // Function to find the minimum
    // of the maximum difference of the
    // adjacent elements after removing
    // K elements from the array
    static int minimumAdjacentDifference(int []a,
                            int n, int k)
    {
        // Intialising the
        // minimum difference
        int minDiff = int.MaxValue;
      
        // Traversing over subsets
        // in iterative manner
        for (int i = 0; i < (1 << n); i++) {
              
            // Number of elements to
            // be taken in the subset
            // ON bits of i represent
            // elements not to be removed
            int cnt = countSetBits(i);
      
            // If the removed
            // set is of size k
            if (cnt == n - k) {
                  
                // Creating the new array
                // after removing elements
                 List<int> temp = new List<int>();
                for (int j = 0; j < n; j++) {
                    if ((i & (1 << j)) != 0)
                        temp.Add(a[j]);
                }
  
                // Maximum difference of adjacent
                // elements of remaining array
                int maxDiff = int.MinValue;
                for (int j = 0; j < temp.Count - 1; j++) {
                    maxDiff = Math.Max(maxDiff,
                    temp[j + 1] - temp[j]);
                }
                minDiff = Math.Min(minDiff, maxDiff);
            }
        }
        return minDiff;
    }
     static int countSetBits(int x)
     {
         int setBits = 0;
         while (x != 0) {
             x = x & (x - 1);
             setBits++;
         }
         return setBits;
     }
    // Driver Code
    public static void Main(String []args)
    {
        int n = 5;
        int k = 2;
      
        int []a = { 3, 7, 8, 10, 14 };
      
        Console.WriteLine(minimumAdjacentDifference(a, n, k));
    }
}
  
// This code is contributed by sapnasingh4991
Output: 
2

 

Сложность времени: O (2 N * N)
Метод 2: Оптимальный подход

  • При внимательном наблюдении можно заметить, что, если удаление элемента выполняется где-то посередине массива (т.е. не из конечных элементов), то максимальная разница между оставшимися элементами может только увеличиваться или оставаться неизменной.
    Например:
 Пусть данный массив равен {1, 5, 6},

Если мы удалим элемент 5 (а не конечный элемент), 
тогда максимальная разница всегда будет увеличиваться.

Поэтому всегда лучше убрать торцевые элементы.
  • Это означает, что результирующий массив после удаления K элементов будет подмассивом исходного массива размером N - K.
  • Следовательно, мы можем перебрать все подмассивы размера N - K и для каждого подмассива найти максимальную разницу между соседними элементами. Наконец, найдите минимум всех максимальных различий соседних элементов.

Below is the implementation of the above approach:

C++

// C++ implementation to find the
// minimum of the maximum difference
// of the adjacent elements after
// removing K elements from the array
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the minimum
// of the maximum difference of the
// adjacent elements after removing
// K elements from the array
int minimumAdjacentDifference(int a[],
                        int n, int k)
{
    // Intialising the
    // minimum difference
    int minDiff = INT_MAX;
 
    // Iterating over all
    // subarrays of size n-k
    for (int i = 0; i <= k; i++) {
         
        // Maximum difference after
        // removing elements
        int maxDiff = INT_MIN;
        for (int j = 0; j < n - k - 1; j++) {
            for (int p = i; p <= i + j; p++) {
                maxDiff = max(maxDiff,
                     a[p + 1] - a[p]);
            }
        }
        // Minimum Adjacent Difference
        minDiff = min(minDiff, maxDiff);
    }
    return minDiff;
}
 
// Driver Code
int main()
{
    int n = 5;
    int k = 2;
 
    int a[n] = { 3, 7, 8, 10, 14 };
 
    cout << minimumAdjacentDifference(a, n, k);
    return 0;
}

Java

// Java implementation to find the
// minimum of the maximum difference
// of the adjacent elements after
// removing K elements from the array
class GFG {
     
    // Function to find the minimum
    // of the maximum difference of the
    // adjacent elements after removing
    // K elements from the array
    static int minimumAdjacentDifference(int a[],
                            int n, int k)
    {
        // Intialising the
        // minimum difference
        int minDiff = Integer.MAX_VALUE;
     
        // Iterating over all
        // subarrays of size n-k
        for (int i = 0; i <= k; i++) {
             
Олимпиады по программированию Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Настройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023