題目

給你一個(gè)下標(biāo)從 1 開始、長(zhǎng)度為 n 的整數(shù)數(shù)組 nums 。

現(xiàn)定義函數(shù) greaterCount ，使得 greaterCount(arr, val) 返回?cái)?shù)組 arr 中 嚴(yán)格大于 val 的元素?cái)?shù)量。

你需要使用 n 次操作，將 nums 的所有元素分配到兩個(gè)數(shù)組 arr1 和 arr2 中。在第一次操作中，將 nums[1] 追加到 arr1 。在第二次操作中，將 nums[2] 追加到 arr2 。之后，在第 i 次操作中：

如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，將 nums[i] 追加到 arr1 。
如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i])，將 nums[i] 追加到 arr2 。
如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，將 nums[i] 追加到元素?cái)?shù)量較少的數(shù)組中。
如果仍然相等，那么將 nums[i] 追加到 arr1 。
連接數(shù)組 arr1 和 arr2 形成數(shù)組 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。

返回整數(shù)數(shù)組 result 。

示例

示例 1

輸入：nums = [2,1,3,3]
輸出：[2,3,1,3]
解釋：在前兩次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，兩個(gè)數(shù)組中大于 3 的元素?cái)?shù)量都是零，并且長(zhǎng)度相等，因此，將 nums[3] 追加到 arr1 。
在第 4 次操作中，兩個(gè)數(shù)組中大于 3 的元素?cái)?shù)量都是零，但 arr2 的長(zhǎng)度較小，因此，將 nums[4] 追加到 arr2 。
在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
因此，連接形成的數(shù)組 result 是 [2,3,1,3] 。

示例 2

輸入：nums = [5,14,3,1,2]
輸出：[5,3,1,2,14]
解釋：在前兩次操作后，arr1 = [5] ，arr2 = [14] 。
在第 3 次操作中，兩個(gè)數(shù)組中大于 3 的元素?cái)?shù)量都是一，并且長(zhǎng)度相等，因此，將 nums[3] 追加到 arr1 。
在第 4 次操作中，arr1 中大于 1 的元素?cái)?shù)量大于 arr2 中的數(shù)量（2 > 1），因此，將 nums[4] 追加到 arr1 。
在第 5 次操作中，arr1 中大于 2 的元素?cái)?shù)量大于 arr2 中的數(shù)量（2 > 1），因此，將 nums[5] 追加到 arr1 。
在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。
因此，連接形成的數(shù)組 result 是 [5,3,1,2,14] 。

示例 3

輸入：nums = [3,3,3,3]
輸出：[3,3,3,3]
解釋：在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。
因此，連接形成的數(shù)組 result 是 [3,3,3,3] 。

提示：

3 <= n <= 105
1 <= nums[i] <= 109

思路

離散化 + 線段樹，由于基礎(chǔ)的線段樹可以AC，不再使用懶標(biāo)記去優(yōu)化。

AC代碼

use std::collections::HashMap;struct Tree{tree: Vec<i32>
}impl Tree {pub fn new(len: usize) -> Self {Tree {tree: vec![0; len]}}/*** 更新**/pub fn update(&mut self, node: usize, sign_idx: usize, l: usize, r: usize) {if l == r {self.tree[node] += 1;return;}let mid: usize = l + r >> 1;let l_node: usize = (node << 1) + 1;let r_node: usize = l_node + 1;if sign_idx <= mid {self.update(l_node, sign_idx, l, mid);} else {self.update(r_node, sign_idx, mid + 1, r);}self.tree[node] = self.tree[l_node] + self.tree[r_node];}/*** 查詢**/pub fn query(&mut self, node: usize, l: usize, r: usize, start: usize, end: usize) -> i32 {if l > end || r < start {return 0;}if l >= start && r <= end {return self.tree[node];}let mid: usize = l + r >> 1;let l_node: usize = (node << 1) + 1;let r_node: usize = l_node + 1;self.query(l_node, l, mid, start, end) + self.query(r_node, mid + 1, r, start, end)}
}impl Solution {pub fn result_array(v: Vec<i32>) -> Vec<i32> {let len: usize = v.len();let tree_len: usize = len << 2;let mut tree1: Tree = Tree::new(tree_len);let mut tree2: Tree = Tree::new(tree_len);let mut arr1: Vec<i32> = vec![v[0]];let mut arr2: Vec<i32> = vec![v[1]];let mut mp: HashMap<usize, usize> = HashMap::new();let mut cp_v: Vec<i32> = v.clone();cp_v.sort();for (idx, tem) in cp_v.iter().enumerate() {mp.insert(*tem as usize, idx);}if let Some(tem_val) = mp.get(&(v[0] as usize)) {tree1.update(0, *tem_val, 0, len - 1);}if let Some(tem_val) = mp.get(&(v[1] as usize)) {tree2.update(0, *tem_val, 0, len - 1);}for idx in 2 .. len {let val: i32 = v[idx];let mut mp_val: usize = 0;if let Some(tem_val) = mp.get(&(val as usize)) {mp_val = *tem_val;}            let s1: i32 = tree1.query(0, 0, len - 1, mp_val + 1, len - 1);let s2: i32 = tree2.query(0, 0, len - 1, mp_val + 1, len - 1);if s1 > s2 {arr1.push(val);tree1.update(0, mp_val, 0, len - 1);continue;}if s2 > s1 {arr2.push(val);tree2.update(0, mp_val, 0, len - 1);continue;}let len1: usize =  arr1.len();let len2: usize = arr2.len();if len1 <= len2 {arr1.push(val);tree1.update(0, mp_val, 0, len - 1);} else {arr2.push(val);tree2.update(0, mp_val, 0, len - 1);}}arr1.extend(arr2);arr1}
}

推薦幾款學(xué)習(xí)編程的免費(fèi)平臺(tái)

免費(fèi)在線開發(fā)平臺(tái)（https://docs.ltpp.vip/LTPP/）

?????? 探索編程世界的新天地，為學(xué)生和開發(fā)者精心打造的編程平臺(tái)，現(xiàn)已盛大開啟！這個(gè)平臺(tái)匯集了近4000道精心設(shè)計(jì)的編程題目，覆蓋了C、C++、JavaScript、TypeScript、Go、Rust、PHP、Java、Ruby、Python3以及C#等眾多編程語言，為您的編程學(xué)習(xí)之旅提供了一個(gè)全面而豐富的實(shí)踐環(huán)境。 ??????
??????在這里，您不僅可以查看自己的代碼記錄，還能輕松地在云端保存和運(yùn)行代碼，讓編程變得更加便捷。平臺(tái)還提供了私聊和群聊功能，讓您可以與同行們無障礙交流，分享文件，共同進(jìn)步。不僅如此，您還可以通過閱讀文章、參與問答板塊和在線商店，進(jìn)一步拓展您的知識(shí)邊界。
?????? 為了提升您的編程技能，平臺(tái)還設(shè)有每日一題、精選題單以及激動(dòng)人心的編程競(jìng)賽，這些都是備考編程考試的絕佳資源。更令人興奮的是，您還可以自定義系統(tǒng)UI，選擇視頻或圖片作為背景，打造一個(gè)完全個(gè)性化的編碼環(huán)境，讓您的編程之旅既有趣又充滿挑戰(zhàn)。

免費(fèi)公益服務(wù)器（https://docs.ltpp.vip/LTPP-SHARE/linux.html）

?????? 作為開發(fā)者或?qū)W生，您是否經(jīng)常因?yàn)榇罱ê途S護(hù)編程環(huán)境而感到頭疼？現(xiàn)在，您不必再為此煩惱，因?yàn)橐豢钊碌拿赓M(fèi)公共服務(wù)器已經(jīng)為您解決了所有問題。這款服務(wù)器內(nèi)置了多種編程語言的編程環(huán)境，并且配備了功能強(qiáng)大的在線版VS Code，讓您可以隨時(shí)隨地在線編寫代碼，無需進(jìn)行任何復(fù)雜的配置。
隨時(shí)隨地，云端編碼
?????? 無論您身在何處，只要有網(wǎng)絡(luò)連接，就可以通過瀏覽器訪問這款公共服務(wù)器，開始您的編程之旅。這種云端編碼的便利性，讓您的學(xué)習(xí)或開發(fā)工作不再受限于特定的設(shè)備或環(huán)境。
豐富的編程語言支持
?????? 服務(wù)器支持包括C、C++、JavaScript、TypeScript、Go、Rust、PHP、Java、Ruby、Python3以及C#等在內(nèi)的多種主流編程語言，滿足不同開發(fā)者和學(xué)生的需求。無論您是初學(xué)者還是資深開發(fā)者，都能找到適合自己的編程環(huán)境。
在線版VS Code，高效開發(fā)
?????? 內(nèi)置的在線版VS Code提供了與本地VS Code相似的編輯體驗(yàn)，包括代碼高亮、智能提示、代碼調(diào)試等功能，讓您即使在云端也能享受到高效的開發(fā)體驗(yàn)。
數(shù)據(jù)隱私和安全提醒
?????? 雖然服務(wù)器是免費(fèi)的，但為了保護(hù)您的數(shù)據(jù)隱私和安全，我們建議您不要上傳任何敏感或重要的數(shù)據(jù)。這款服務(wù)器更適合用于學(xué)習(xí)和實(shí)驗(yàn)，而非存儲(chǔ)重要信息。

免費(fèi)公益MYSQL（https://docs.ltpp.vip/LTPP-SHARE/mysql.html）

?????? 作為一名開發(fā)者或?qū)W生，數(shù)據(jù)庫(kù)環(huán)境的搭建和維護(hù)往往是一個(gè)復(fù)雜且耗時(shí)的過程。但不用擔(dān)心，現(xiàn)在有一款免費(fèi)的MySQL服務(wù)器，專為解決您的煩惱而設(shè)計(jì)，讓數(shù)據(jù)庫(kù)的使用變得簡(jiǎn)單而高效。
性能卓越，滿足需求
?????? 雖然它是免費(fèi)的，但性能絕不打折。服務(wù)器提供了穩(wěn)定且高效的數(shù)據(jù)庫(kù)服務(wù)，能夠滿足大多數(shù)開發(fā)和學(xué)習(xí)場(chǎng)景的需求。
在線phpMyAdmin，管理更便捷
?????? 內(nèi)置的在線phpMyAdmin管理面板，提供了一個(gè)直觀且功能強(qiáng)大的用戶界面，讓您可以輕松地查看、編輯和管理數(shù)據(jù)庫(kù)。
數(shù)據(jù)隱私提醒，安全第一
?????? 正如您所知，這是一項(xiàng)公共資源，因此我們強(qiáng)烈建議不要上傳任何敏感或重要的數(shù)據(jù)。請(qǐng)將此服務(wù)器僅用于學(xué)習(xí)和實(shí)驗(yàn)?zāi)康?#xff0c;以確保您的數(shù)據(jù)安全。

免費(fèi)在線WEB代碼編輯器（https://docs.ltpp.vip/LTPP-WEB-IDE/）

?????? 無論你是開發(fā)者還是學(xué)生，編程環(huán)境的搭建和管理可能會(huì)占用你寶貴的時(shí)間和精力?，F(xiàn)在，有一款強(qiáng)大的免費(fèi)在線代碼編輯器，支持多種編程語言，讓您可以隨時(shí)隨地編寫和運(yùn)行代碼，提升編程效率，專注于創(chuàng)意和開發(fā)。
多語言支持，無縫切換
?????? 這款在線代碼編輯器支持包括C、C++、JavaScript、TypeScript、Go、Rust、PHP、Java、Ruby、Python3以及C#在內(nèi)的多種編程語言，無論您的項(xiàng)目需要哪種語言，都能在這里找到支持。
在線運(yùn)行，快速定位問題
?????? 您可以在編寫代碼的同時(shí)，即時(shí)運(yùn)行并查看結(jié)果，快速定位并解決問題，提高開發(fā)效率。
代碼高亮與智能提示
?????? 編輯器提供代碼高亮和智能提示功能，幫助您更快地編寫代碼，減少錯(cuò)誤，提升編碼質(zhì)量。

免費(fèi)二維碼生成器（https://docs.ltpp.vip/LTPP-QRCODE/）

?????? 二維碼（QR Code）是一種二維條碼，能夠存儲(chǔ)更多信息，并且可以通過智能手機(jī)等設(shè)備快速掃描識(shí)別。它廣泛應(yīng)用于各種場(chǎng)景，如：
企業(yè)宣傳
?????? 企業(yè)可以通過二維碼分享公司網(wǎng)站、產(chǎn)品信息、服務(wù)介紹等。
活動(dòng)推廣
?????? 活動(dòng)組織者可以創(chuàng)建二維碼，參與者掃描后可以直接訪問活動(dòng)詳情、報(bào)名鏈接或獲取電子門票。
個(gè)人信息分享
?????? 個(gè)人可以生成包含聯(lián)系方式、社交媒體鏈接、個(gè)人簡(jiǎn)歷等信息的二維碼。
電子商務(wù)
?????? 商家使用二維碼進(jìn)行商品追蹤、促銷活動(dòng)、在線支付等。
教育
?????? 教師可以創(chuàng)建二維碼，學(xué)生掃描后可以直接訪問學(xué)習(xí)資料或在線課程。
交通出行
?????? 二維碼用于公共交通的票務(wù)系統(tǒng)，乘客掃描二維碼即可進(jìn)出站或支付車費(fèi)。 ?????? 功能強(qiáng)大的二維碼生成器通常具備用戶界面友好，操作簡(jiǎn)單，即使是初學(xué)者也能快速上手和生成的二維碼可以在各種設(shè)備和操作系統(tǒng)上掃描識(shí)別的特點(diǎn)。