本文概述
- 建议:在继续解决方案之前, 请先在"实践"上解决它。
- C ++
- Java
- Python3
- C#
- 的PHP
例子:
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#
// 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(登录)。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- Scala中的匿名函数详细介绍
- C#逐字字符串字面量– @用法介绍
- PHP gmp_div_qr()函数用法详细介绍
- 端口地址转换(PAT)映射到专用IP详细介绍
- Salesforce面试经验|在校园
- 操作系统常见问题集锦和答案|S10
- 操作系统常见问题和答案合集|S11
- 操作系统常见问题和考试问题|S12
- 操作系统相关考试问题|S13