專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
4月5日中核集團(tuán)發(fā)布了一篇文章，標(biāo)題是：我們收到1196273份簡歷，當(dāng)然收到那么多簡歷對(duì)企業(yè)來說肯定是好事，收到的簡歷多說明企業(yè)的受關(guān)注度高，熱度高。但站在求職者的角度來說肯定不是啥好事，因?yàn)檫@意味著就業(yè)壓力大，競爭也比較激烈。
按說一個(gè)央企收到這么多簡歷也不足為怪，畢竟現(xiàn)在這個(gè)階段，很多人還是希望能進(jìn)入到國企或者央企，找一份穩(wěn)定的工作，關(guān)鍵是他這文章的標(biāo)題再加上標(biāo)題后面的表情，讓網(wǎng)友感覺盡顯傲慢之態(tài)。發(fā)文之后很快遭到網(wǎng)友的熱議隨后又把文章給刪了。
然后第二天4月6日再度發(fā)文稱：我們始終堅(jiān)持認(rèn)真對(duì)待每份簡歷，不辜負(fù)每位學(xué)子對(duì)我們的認(rèn)可和信任”，并解釋該集團(tuán)2025屆校招“提供1730類崗位，預(yù)計(jì)錄用人數(shù)約8000人”，每位學(xué)子可以投遞20個(gè)崗位。
將近200萬份簡歷就算所有人全部投遞20個(gè)崗位也有10萬人，如果人均投遞2個(gè)崗位大概有100萬人，究竟有多少人我們不得而知，反正簡歷大概是200萬份。企業(yè)受追捧是好事，但數(shù)字背后承載的期待更值得被看見。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1403題：非遞增順序的最小子序列，難度是簡單。
給你一個(gè)數(shù)組 nums，請(qǐng)你從中抽取一個(gè)子序列，滿足該子序列的元素之和 嚴(yán)格大于未包含在該子序列中的各元素之和。
如果存在多個(gè)解決方案，只需返回長度最小的子序列。如果仍然有多個(gè)解決方案，則返回元素之和最大的子序列。
示例1：
輸入：nums = [4,3,10,9,8] 輸出：[10,9] 解釋：子序列 [10,9] 和 [10,8] 是最小的、滿足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。
示例2：
輸入：nums = [4,4,7,6,7] 輸出：[7,7,6] 解釋：子序列 [7,7] 的和為 14 ，不嚴(yán)格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是滿足題意的最小子序列。注意，元素按非遞增順序返回。
1 <= nums.length <= 500
1 <= nums[i] <= 100
問題分析
這題說的是從數(shù)組中選擇一些數(shù)字，且選擇的數(shù)字之和大于未選擇的數(shù)字之和，如果存在多個(gè)答案，要返回選擇數(shù)字最少的，如果還存在多個(gè)答案，要返回?cái)?shù)字之和最大的。
這題并沒有說不能打亂選擇的順序，所以我們可以先對(duì)數(shù)組排序，然后從大道小選擇，直到選擇的數(shù)字之和大于剩余數(shù)字之和即可，所以這題比較簡單，我們可以直接模擬。
JAVA：
public List minSubsequence(int[] nums) { Arrays.sort(nums);// 先對(duì)數(shù)組排序 int sum = 0;// 累加所有元素的和。 for (int num : nums) sum += num; List ans = new ArrayList<>(); int cur = 0;// 記錄已經(jīng)選擇的元素和 // 逆序從最大的開始選擇 for (int i = nums.length - 1; i >= 0; i--) { ans.add(nums[i]); cur += nums[i]; // 如果已經(jīng)選擇的大于未選擇的，則終止。 if (cur > sum - cur) break; } return ans; }C++：
public: vector
minSubsequence(vector
&nums) { sort(nums.begin(), nums.end());// 先對(duì)數(shù)組排序 int sum = 0;// 累加所有元素的和。 for (int num: nums) sum += num; vector
ans; int cur = 0;// 記錄已經(jīng)選擇的元素和 // 逆序從最大的開始選擇 for (int i = nums.size() - 1; i >= 0; i--) { ans.push_back(nums[i]); cur += nums[i]; // 如果已經(jīng)選擇的大于未選擇的，則終止。 if (cur > sum - cur) break; } return ans; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼