最近一網(wǎng)友發(fā)文稱自己是雙非院校計(jì)算機(jī)專業(yè)，在北京找了一份實(shí)習(xí)的工作，每天早起通勤擠地鐵到公司上班，可現(xiàn)在學(xué)校不讓住外面、也不讓外出實(shí)習(xí)，對(duì)于私自外出實(shí)習(xí)的要受到處分。

對(duì)于這種情況，很多網(wǎng)友表示很無語，私自外出實(shí)習(xí)，學(xué)校怕出事?lián)?zé)。如果不外出實(shí)習(xí)，留在學(xué)校又沒有工作，啥項(xiàng)目經(jīng)驗(yàn)也學(xué)不到，對(duì)于這種情況竟然有不少同學(xué)遇到過。

我記得我當(dāng)年快畢業(yè)的時(shí)候雖然學(xué)校沒有鼓勵(lì)我們?nèi)バＭ饷鎸?shí)習(xí)，但也沒禁止我們外出，出去實(shí)習(xí)學(xué)校也是睜一只眼閉一只眼。因?yàn)槿绻粚?shí)習(xí)的話，到時(shí)候畢業(yè)可能暫時(shí)找不到工作，學(xué)生的就業(yè)率低，又會(huì)影響到學(xué)校的排名。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1509題：三次操作后最大值與最小值的最小差，難度是中等。

給你一個(gè)數(shù)組 nums 。每次操作你可以選擇 nums 中的任意一個(gè)元素并將它改成任意值 。在執(zhí)行最多三次移動(dòng)后 ，返回 nums 中最大值與最小值的最小差值。

示例1：

輸入：nums = [5,3,2,4] 輸出：0 解釋：我們最多可以走 3 步。 第一步，將 2 變?yōu)?3 。 nums 變成 [5,3,3,4] 。 第二步，將 4 改為 3 。 nums 變成 [5,3,3,3] 。 第三步，將 5 改為 3 。 nums 變成 [3,3,3,3] 。 執(zhí)行 3 次移動(dòng)后，最小值和最大值之間的差值為 3 - 3 = 0 。

示例2：

輸入：nums = [1,5,0,10,14] 輸出：1 解釋：我們最多可以走 3 步。 第一步，將 5 改為 0 。 nums變成 [1,0,0,10,14] 。 第二步，將 10 改為 0 。 nums變成 [1,0,0,0,14] 。 第三步，將 14 改為 1 。 nums變成 [1,0,0,0,1] 。 執(zhí)行 3 步后，最小值和最大值之間的差值為 1 - 0 = 1 。 可以看出，沒有辦法可以在 3 步內(nèi)使差值變?yōu)?。

• 1 <= nums.length <= 10^5

• -10^9 <= nums[i] <= 10^9

問題分析

這題說的是每次操作可以把數(shù)組中的任意一個(gè)元素變成任意值，最多執(zhí)行 3 次操作，3 次操作之后，計(jì)算數(shù)組中最大值和最小值的差值。

如果數(shù)組中的元素個(gè)數(shù)小于等于 4 ，我們可以把數(shù)組中其他所有元素的值都改成第一個(gè)元素的值，這樣數(shù)組中所有元素都一樣了，這時(shí)候數(shù)組中最大值和最小值的差值是 0 。

如果數(shù)組中的元素個(gè)數(shù)大于 4 ，我們先對(duì)數(shù)組排序，排序之后要想數(shù)組中最大值和最小值的差值最小，我們可以移除 3 個(gè)元素，然后用數(shù)組中的最大值減去最小值。

怎么移除？可以移除最小的，也可以移除最大的，我們只需要保存差值的最小值即可。

JAVA：

public int minDifference(int[] nums) {     int n = nums.length;     if (n <= 4)         return 0;     Arrays.sort(nums);     int ans = Integer.MAX_VALUE;     ans = Math.min(ans, nums[n - 1] - nums[3]);// 前面移除 3 個(gè)，后面移除 0 個(gè)     ans = Math.min(ans, nums[n - 2] - nums[2]);// 前面移除 2 個(gè)，后面移除 1 個(gè)     ans = Math.min(ans, nums[n - 3] - nums[1]);// 前面移除 1 個(gè)，后面移除 2 個(gè)     ans = Math.min(ans, nums[n - 4] - nums[0]);// 前面移除 0 個(gè)，后面移除 3 個(gè)     return ans; }

C++：

public:     int minDifference(vector
               
 &nums) {         int n = nums.size();         if (n <= 4)             return 0;         sort(nums.begin(), nums.end());         int ans = INT_MAX;         ans = min(ans, nums[n - 1] - nums[3]);// 前面移除 3 個(gè)，后面移除 0 個(gè)         ans = min(ans, nums[n - 2] - nums[2]);// 前面移除 2 個(gè)，后面移除 1 個(gè)         ans = min(ans, nums[n - 3] - nums[1]);// 前面移除 1 個(gè)，后面移除 2 個(gè)         ans = min(ans, nums[n - 4] - nums[0]);// 前面移除 0 個(gè)，后面移除 3 個(gè)         return ans;     }
       

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧 。