算法题：选择k个数组元素，使最大值和最小值之差最小

本文概述

• 建议：在继续解决方案之前, 请先在"实践"上解决它。
• C ++
• Java
• Python3
• C#
• 的PHP

给定一个数组n整数和正数k。我们被允许从给定的数组中获取任何k个整数。任务是找到K个数的最大值和最小值之间的差的最小可能值。

例子：

Input : arr[] = {10, 100, 300, 200, 1000, 20, 30}
        k = 3
Output : 20
20 is the minimum possible difference between any
maximum and minimum of any k numbers.
Given k = 3, we get the result 20 by selecting 
integers {10, 20, 30}.
max(10, 20, 30) - max(10, 20, 30) = 30 - 10 = 20.

Input : arr[] = {1, 2, 3, 4, 10, 20, 30, 40, 100, 200}.
        k = 4      
Output : 3

推荐：请在"实践首先, 在继续解决方案之前。

这个想法是对数组排序并选择k个连续整数。为什么要连续？令所选的k个整数为arr [0], arr [1], .. arr [r], arr [r + x]…, arr [k-1], 它们在排序数组中都以递增顺序但不连续。这意味着在arr [r]和arr [r + x]之间存在一个整数p。因此, 如果包含p并删除arr [0], 则新的差异将是arr [r] – arr [1], 而旧的差异将是arr [r] – arr [0]。而且我们知道arr [0] <= arr [1] <= .. <= arr [k-1], 因此最小差异减小或保持不变。如果我们对其他像p的数字执行相同的过程, 则得到的差异最小。

解决问题的算法：

1. 排序数组。
2. 计算每组k个连续整数的最大值(k个数)-最小值(k个数)。
3. 返回在步骤2中获得的所有值的最小值。

下面是上述想法的实现：

C ++

// C++ program to find minimum difference of maximum
// and minimum of K number.
#include<bits/stdc++.h>
using namespace std;
  
// Return minimum difference of maximum and minimum
// of k elements of arr[0..n-1].
int minDiff( int arr[], int n, int k)
{
     int result = INT_MAX;
  
     // Sorting the array.
     sort(arr, arr + n);
  
     // Find minimum value among all K size subarray.
     for ( int i=0; i<=n-k; i++)
         result = min(result, arr[i+k-1] - arr[i]);
  
     return result;
}
  
// Driven Program
int main()
{
     int arr[] = {10, 100, 300, 200, 1000, 20, 30};
     int n = sizeof (arr)/ sizeof (arr[0]);
     int k = 3;
  
     cout << minDiff(arr, n, k) << endl;
     return 0;
}

Java

// Java program to find minimum difference 
// of maximum and minimum of K number.
import java.util.*;
  
class GFG {
      
// Return minimum difference of 
// maximum and minimum of k 
// elements of arr[0..n-1].
static int minDiff( int arr[], int n, int k) {
     int result = Integer.MAX_VALUE;
  
     // Sorting the array.
     Arrays.sort(arr);
  
     // Find minimum value among 
     // all K size subarray.
     for ( int i = 0 ; i <= n - k; i++)
     result = Math.min(result, arr[i + k - 1 ] - arr[i]);
  
     return result;
}
  
// Driver code
public static void main(String[] args) {
     int arr[] = { 10 , 100 , 300 , 200 , 1000 , 20 , 30 };
     int n = arr.length;
     int k = 3 ;
  
     System.out.println(minDiff(arr, n, k));
}
}
  
// This code is contributed by Anant Agarwal.

Python3

# Python program to find minimum
# difference of maximum
# and minimum of K number.
  
# Return minimum difference
# of maximum and minimum
# of k elements of arr[0..n-1].
def minDiff(arr, n, k):
     result = + 2147483647
   
     # Sorting the array.
     arr.sort()
   
     # Find minimum value among
     # all K size subarray.
     for i in range (n - k + 1 ):
         result = int ( min (result, arr[i + k - 1 ] - arr[i]))
   
     return result
  
# Driver code
  
arr = [ 10 , 100 , 300 , 200 , 1000 , 20 , 30 ]
n = len (arr)
k = 3
   
print (minDiff(arr, n, k))
  
# This code is contributed
# by Anant Agarwal.

C#

// C# program to find minimum
// difference of maximum and 
// minimum of K number.
using System;
  
class GFG {
      
// Return minimum difference of 
// maximum and minimum of k 
// elements of arr[0..n - 1].
static int minDiff( int []arr, int n, int k) 
{
     int result = int .MaxValue;
  
     // Sorting the array.
     Array.Sort(arr);
  
     // Find minimum value among 
     // all K size subarray.
     for ( int i = 0; i <= n - k; i++)
     result = Math.Min(result, arr[i + k - 1] - arr[i]);
  
     return result;
}
  
// Driver code
public static void Main() {
     int []arr = {10, 100, 300, 200, 1000, 20, 30};
     int n = arr.Length;
     int k = 3;
  
     Console.WriteLine(minDiff(arr, n, k));
}
}
  
// This code is contributed by vt_m.

的PHP

<?php
// PHP program to find minimum
// difference of maximum and 
// minimum of K number.
  
// Return minimum difference 
// of maximum and minimum
// of k elements of arr[0..n-1].
function minDiff( $arr , $n , $k )
{
     $INT_MAX = 2147483647;
     $result = $INT_MAX ;
  
     // Sorting the array.
     sort( $arr , $n );
     sort( $arr ); 
  
     // Find minimum value among
     // all K size subarray.
     for ( $i = 0; $i <= $n - $k ; $i ++)
         $result = min( $result , $arr [ $i + $k - 1] - 
                                        $arr [ $i ]);
     return $result ;
}
  
     // Driver Code
     $arr = array (10, 100, 300, 200, 1000, 20, 30);
     $n = sizeof( $arr );
     $k = 3;
     echo minDiff( $arr , $n , $k );
      
// This code is contributed by nitin mittal.
?>

输出如下：

20

时间复杂度：O(登录)。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。