算法题（选择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个连续整数。为什么要连续？令所选的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的数字执行相同的过程, 则得到的差异最小。
解决问题的算法：

排序数组。
计算每组k个连续整数的最大值(k个数)-最小值(k个数)。
返回在步骤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 codearr = [ 10 , 100 , 300 , 200 , 1000 , 20 , 30 ] n = len (arr) k = 3print (minDiff(arr, n, k))# This code is contributed # by Anant Agarwal.

// 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. ?>

输出如下：