将两个高度之间的最大差异降至最低-yiteyi-C++库

给定n个塔的高度和一个值k。我们需要将每个塔的高度增加或减少k（仅一次），其中k>0。任务是在修改后将最长和最短塔的高度差降至最低，并输出该差。 例如：

null

Input  : arr[] = {1, 15, 10}, k = 6Output :  Maximum difference is 5.Explanation : We change 1 to 7, 15 to 9 and 10 to 4. Maximum difference is 5(between 4 and 9). We can't get a lowerdifference.Input : arr[] = {1, 5, 15, 10}         k = 3   Output : Maximum difference is 8arr[] = {4, 8, 12, 7}Input : arr[] = {4, 6}         k = 10Output : Maximum difference is 2arr[] = {14, 16} OR {-6, -4}Input : arr[] = {6, 10}         k = 3Output : Maximum difference is 2arr[] = {9, 7} Input : arr[] = {1, 10, 14, 14, 14, 15}        k = 6 Output: Maximum difference is 5arr[] = {7, 4, 8, 8, 8, 9} Input : arr[] = {1, 2, 3}        k = 2 Output: Maximum difference is 2arr[] = {3, 4, 5}

资料来源： Adobe面试体验|第24集（MTS校园）

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

首先，我们尝试对阵列进行排序，并使每个塔的高度最大。我们通过将所有塔楼的高度向右降低k，并将所有塔楼的高度向左增加k来实现这一点。你试图增加高度的塔也可能没有最大高度。因此，我们只需将其与右侧的最后一个元素（a[n]-k）进行比较，来检查它是否具有最大高度。因为阵列是排序的，如果塔的高度大于a[n]-k，那么它就是可用的最高塔。类似的推理也可用于寻找最短的塔。

注意：我们不需要考虑在哪里[i]＜k，因为塔的高度不能是负的，所以我们必须忽略这种情况。

时间复杂性： O（nlogn）

空间复杂性： O（n）

C++

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // User function Template                       
                         int                                     getMinDiff(                                     int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 sort(arr, arr + n);                       
                                                 int                                     ans = arr[n - 1] - arr[0];                                     // Maximum possible height difference                       
           
                                                 int                                     tempmin, tempmax;                       
                                                 tempmin = arr[0];                       
                                                 tempmax = arr[n - 1];                       
           
                                                 for                                     (                                     int                                     i = 1; i < n; i++) {                       
                                                 tempmin= min(arr[0] + k,arr[i] - k);                                     // Minimum element when we                       
                                                 // add k to whole array                       
                                                 tempmax = max(arr[i - 1] + k, arr[n - 1] - k);                                     // Maximum element when we                       
                                                 // subtract k from whole array                       
                                                 ans = min(ans, tempmax - tempmin);                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver Code Starts                       
                         int                                     main()                       
                         {                       
                                                 int                                     k = 6, n = 6;                       
                                                 int                                     arr[n] = { 7, 4, 8, 8, 8, 9 };                       
                                                 int                                     ans = getMinDiff(arr, n, k);                       
                                                 cout << ans;                       
                         }                       

JAVA

                         /*package whatever //do not write package name here */                       
           
                         // { Driver Code Starts                       
                         // Initial Template for Java                       
           
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         public                                     class                                     Main {                       
           
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     [] arr = {                                     7                                     ,                                     4                                     ,                                     8                                     ,                                     8                                     ,                                     8                                     ,                                     9                                     };                       
                                                 int                                     k =                                     6                                     ;                       
                                                 int                                     ans = getMinDiff(arr, arr.length, k);                       
                                                 System.out.println(ans);                       
                                                 }                       
                                                 // } Driver Code Ends                       
           
                                                 // User function Template for Java                       
           
                                                 public                                     static                                     int                                     getMinDiff(                                     int                                     [] arr,                                     int                                     n,                                     int                                     k)                       
                                                 {                       
           
                                                 Arrays.sort(arr);                       
                                                 int                                     ans = (arr[n -                                     1                                     ] + k)- (arr[                                     0                                     ] + k);                                     // Maximum possible height difference                       
           
                                                 int                                     tempmax = arr[n -                                     1                                     ] - k;                                     // Maximum element when we                       
                                                 // subtract k from whole array                       
                                                 int                                     tempmin = arr[                                     0                                     ] + k;                                     // Minimum element when we                       
                                                 // add k to whole array                       
                                                 int                                     max, min;                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n -                                     1                                     ; i++) {                       
                                                 if                                     (tempmax > (arr[i] + k)) {                       
                                                 max = tempmax;                       
                                                 }                       
                                                 else                                     {                       
                                                 max = arr[i] + k;                       
                                                 }                       
           
                                                 if                                     (tempmin < (arr[i +                                     1                                     ] - k)) {                       
                                                 min = tempmin;                       
                                                 }                       
                                                 else                                     {                       
                                                 min = arr[i +                                     1                                     ] - k;                       
                                                 }                       
           
                                                 if                                     (ans > (max - min)) {                       
                                                 ans = max - min;                       
                                                 }                       
                                                 }                       
                                                 return                                     ans;                       
                                                 }                       
                         }                       

Python3

                         # User function Template                       
                         def                                     getMinDiff(arr, n, k):                       
                                                 arr.sort()                       
                                                 ans                                     =                                     arr[n                                     -                                     1                                     ]                                     -                                     arr[                                     0                                     ]                                     # Maximum possible height difference                       
           
                                                 tempmin                                     =                                     arr[                                     0                                     ]                       
                                                 tempmax                                     =                                     arr[n                                     -                                     1                                     ]                       
           
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                                 tempmin                                     =                                     min                                     (arr[                                     0                                     ]                                     +                                     k, arr[i]                                     -                                     k)                       
                                   
                                                 # Minimum element when we                       
                                                 # add k to whole array                       
                                                 # Maximum element when we                       
                                                 tempmax                                     =                                     max                                     (arr[i                                     -                                     1                                     ]                                     +                                     k, arr[n                                     -                                     1                                     ]                                     -                                     k)                       
                                   
                                                 # subtract k from whole array                       
                                                 ans                                     =                                     min                                     (ans, tempmax                                     -                                     tempmin)                       
           
                                                 return                                     ans                       
           
                         # Driver Code Starts                       
                         k                                     =                                     6                       
                         n                                     =                                     6                       
                         arr                                     =                                     [                                     7                                     ,                                     4                                     ,                                     8                                     ,                                     8                                     ,                                     8                                     ,                                     9                                     ]                       
                         ans                                     =                                     getMinDiff(arr, n, k)                       
                         print                                     (ans)                       
           
                         # This code is contributed by ninja_hattori.                       

Javascript

                         <script>                       
           
                         // User function Template                       
                         function                                     getMinDiff(arr,n,k)                       
                         {                       
                                                 arr.sort((a,b) => (a-b))                       
                                                 let ans = arr[n - 1] - arr[0];                                     // Maximum possible height difference                       
           
                                                 let tempmin, tempmax;                       
                                                 tempmin = arr[0];                       
                                                 tempmax = arr[n - 1];                       
           
                                                 for                                     (let i = 1; i < n; i++) {                       
                                                 tempmin= Math.min(arr[0] + k,arr[i] - k);                                     // Minimum element when we                       
                                                 // add k to whole array                       
                                                 tempmax = Math.max(arr[i - 1] + k, arr[n - 1] - k);                                     // Maximum element when we                       
                                                 // subtract k from whole array                       
                                                 ans = Math.min(ans, tempmax - tempmin);                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver Code Starts                       
                         let k = 6, n = 6;                       
                         let arr = [ 7, 4, 8, 8, 8, 9 ];                       
                         let ans = getMinDiff(arr, n, k);                       
                         document.write(ans,                                     "</br>"                                     );                       
           
                         //This code is contributed by shinjanpatra.                       
                         </script>                       

输出

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章