力扣373. 查找和最小的 K 對數字

優先隊列

  • 思路:
    • 使用下標 (x, y) 標識數值對,x 為第一個數組的下標,y 為第二個數組的下標;
    • 所以 k 個數值對 x 的范圍屬于 [0, min(k, m)],m 為第一個數組的 size;
    • 數值對 (x, y) ,那么下一個比其大的數組對是 min{(x, y + 1), (x + 1, y)};
    • 可以先固定 x ,即將 x 可能的值全選,來動態變更 y;
    • 構建一個優先隊列,存放的是 (x, y),小頂堆,即其對應的數值對的和最小的總是在堆頂:nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
    • 將小頂堆取 k 次堆頂即可,每次之后將 (x, y + 1) 入堆即可;
class Solution {
public:vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {auto cmp = [&nums1, &nums2](const std::pair<int, int>& a, const std::pair<int, int>& b) {return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];};int m = nums1.size();int n = nums2.size();std::vector<std::vector<int>> result;std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(cmp)> pq(cmp);for (int i = 0; i < std::min(k, m); i++) {pq.emplace(i, 0);}while (k-- > 0 && !pq.empty()) {auto [x, y] = pq.top();pq.pop();result.push_back(std::initializer_list<int>{nums1[x], nums2[y]});if (y + 1 < n) {pq.emplace(x, y + 1);}}return result;}
};

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/213259.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/213259.shtml
英文地址,請注明出處:http://en.pswp.cn/news/213259.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

TailwindCSS 如何處理RTL布局模式

背景 TikTok作為目前全世界最受歡迎的APP&#xff0c;需要考慮兼容全世界各個地區的本地化語言和閱讀習慣。其中對于阿拉伯語、波斯語等語言的閱讀書寫習慣是從右向左的&#xff0c;在前端有一個專有名字RTL模式&#xff0c;即Right-to-Left。 其中以阿拉伯語作為第一語言的人…

C# 獲取windows 系統開關機時間

關機時間&#xff0c;引用&#xff1a;https://www.coder.work/article/1589448 public static DateTime GetLastSystemShutdown() { string sKey "System\CurrentControlSet\Control\Windows"; Microsoft.Win32.RegistryKey key …

建立個人學習觀|地鐵上的自習室

作者&#xff1a;向知 如果大家有機會來北京&#xff0c;可以來看看工作日早上八九點鐘&#xff0c;15 號線從那座叫“順義”的城市通向“望京”的地鐵&#xff0c;你在那上面&#xff0c;能看到明明白白的&#xff0c;人們奔向夢想的模樣。 一、地鐵上的自習室 我在來北京之前…

華為數據之道學習筆記】3-5 規則數據治理

在業務規則管理方面&#xff0c;華為經常面對“各種業務場景業務規則不同&#xff0c;記不住&#xff0c;找不到”“大量規則在政策、流程等文件中承載&#xff0c;難以遵守”“各國規則均不同&#xff0c;IT能否一國一策、快速上線”等問題。 規則數據是結構化描述業務規則變量…

【算法集訓】基礎數據結構:三、鏈表

鏈表就是將所有數據都用一個鏈子串起來&#xff0c;其中鏈表也有多種形式&#xff0c;包含單向鏈表、雙向鏈表等&#xff1b; 現在畢竟還是基礎階段&#xff0c;就先學習單鏈表吧&#xff1b; 鏈表用頭結點head表示一整個鏈表&#xff0c;每個鏈表的節點包含當前節點的值val和下…

2024 年頂級的 Android 系統修復軟件與方法

您是否正在尋找可以修復 PC 上 Android 操作系統的工具&#xff1f;這是我們精選的最好的 Android 系統修復軟件&#xff01; Android 是世界著名的智能手機操作系統。全世界有數百萬人使用這個操作系統&#xff0c;這使得它安全可靠。然而&#xff0c;這仍然不能使它完美無缺…

048:利用vue-video-player播放m3u8

第048個 查看專欄目錄: VUE ------ element UI 專欄目標 在vue和element UI聯合技術棧的操控下&#xff0c;本專欄提供行之有效的源代碼示例和信息點介紹&#xff0c;做到靈活運用。 &#xff08;1&#xff09;提供vue2的一些基本操作&#xff1a;安裝、引用&#xff0c;模板使…

普冉(PUYA)單片機開發筆記(6): 呼吸燈

概述 上一篇的實驗中&#xff0c;分別正確地配置了 TIM16 和 TIM1&#xff0c;TIM16 的中斷服務程序中每隔 500ms 翻轉板載 LED 一次&#xff1b;TIM1 的 CHANNEL_1 用于輸出一個固定占空比的 PWM 信號。這一次我們進一小步&#xff1a;使用 TIM16 的中斷設置 TIM1 CHANNEL_1 …

MyBatis進階之分頁和延遲加載

文章目錄 分頁1. RowBounds 分頁2. PageHelper 分頁3. PageInfo 對象屬性描述 延遲加載立即加載激進式延遲加載真-延遲加載 分頁 Mybatis 中實現分頁功能有 3 種途徑&#xff1a; RowBounds 分頁&#xff08;不建議使用&#xff09;Example 分頁&#xff08;簡單情況可用)Pag…

關于對向量檢索研究的一些學習資料整理

官方學習資料 主要是的學習資料是&#xff0c; 官方文檔 和官方博客。相關文章還是挺多 挺不錯的 他們更新也比較及時。有最新的東西 都會更新出來。es scdn官方博客 這里簡單列一些&#xff0c;還有一些其他的&#xff0c;大家自己感興趣去看。 什么是向量數據庫 Elasticse…

文件加密軟件哪個最好用 好用的文件加密軟件推薦

一說到文件加密軟件&#xff0c;可能大家都會去搜一些不知名的軟件來&#xff0c;但是選擇這種加密軟件&#xff0c;最好還是要看一些資質的。 資質不好的&#xff0c;可能加密過后你自己也打不開文件&#xff0c;&#xff08;ps&#xff1a;我自己就遇到過這種情況&#xff09…

【華為OD機試python】分蘋果【2023 B卷|100分】

【華為OD機試】-真題 !!點這里!! 【華為OD機試】真題考點分類 !!點這里 !! 題目描述 A、B兩個人把蘋果分為兩堆,A希望按照他的計算規則等分蘋果, 他的計算規則是按照二進制加法計算,并且不計算進位 12+5=9(1100 + 0101 = 9), B的計算規則是十進制加法,包括正常進位,…

基于Java SSM框架高校校園點餐訂餐系統項目【項目源碼+論文說明】計算機畢業設計

基于java的SSM框架高校校園點餐訂餐系統演示 摘要 21世紀的今天&#xff0c;隨著社會的不斷發展與進步&#xff0c;人們對于信息科學化的認識&#xff0c;已由低層次向高層次發展&#xff0c;由原來的感性認識向理性認識提高&#xff0c;管理工作的重要性已逐漸被人們所認識&a…

(一)Java 基礎語法

目錄 一. 前言 二. Hello World 三. Java 語法 3.1. 基本語法 3.2. Java 標識符 3.3. Java 修飾符 3.4. Java 變量 3.5. Java 數組 3.6. Java 枚舉 3.7. Java 關鍵字 3.8. Java 注釋 3.9. Java 空行 3.10. Java 繼承 3.11. Java 接口&#xff08;interface&#…

Oracle(2-14)User-Managed Incomplete Recovery

文章目錄 一、基礎知識1、Incomplete Recovery Overview 不完全恢復概述2、Situations Requiring IR 需要不完全恢復的情況3、Types of IR 不完全恢復的類型4、IR Guidelines 不完全恢復指南5、User-Managed Procedures 用戶管理程序6、RECOVER Command Overview 恢復命令概述7…

算法訓練營Day8(字符串)

344.反轉字符串 344. 反轉字符串 - 力扣&#xff08;LeetCode&#xff09; class Solution {public void reverseString(char[] s) {for(int i 0,j s.length-1;i< s.length/2 ; i,j--){swap(s,i,j);}}public void swap(char[] s,int i,int j ){char temp s[i];s[i] s[j]…

Python數據科學視頻講解:Python注釋

2.3 Python注釋 視頻為《Python數據科學應用從入門到精通》張甜 楊維忠 清華大學出版社一書的隨書贈送視頻講解2.3節內容。本書已正式出版上市&#xff0c;當當、京東、淘寶等平臺熱銷中&#xff0c;搜索書名即可。內容涵蓋數據科學應用的全流程&#xff0c;包括數據科學應用和…

20231210原始編譯NanoPC-T4(RK3399)開發板的Android10的SDK

20231210原始編譯NanoPC-T4(RK3399)開發板的Android10的SDK 2023/12/10 17:27 rootrootrootroot-X99-Turbo:~$ rootrootrootroot-X99-Turbo:~$ mkdir nanopc-t4 rootrootrootroot-X99-Turbo:~$ rootrootrootroot-X99-Turbo:~$ rootrootrootroot-X99-Turbo:~$ cd nanopc-t4/ …

python4E 之 Dict 找到兩個不同索引但都需要對應的值。

找到兩個不同索引但都需要&#xff0c;對應的值。 df pd.DataFrame(np.random.randint(1, 10, [3,3]), columns list(ABC)) 通過 dict 制造key index_htable{} for _,row in idc.iterrows(): #按行循環 key str(row[u股票代碼]) | str(row[u日期]) #根據不同 的索引…

45.0/HTML 簡介(詳細版)

目錄 45.1 互聯網簡介 45.2 網頁技術與分類 45.3 HTML 簡介 45.3.1 什么是 HTML?(面試題) 45.3.2 HTML 文件結構 45.3.3 HTML 語法 45.3.4 實例演練步驟(面試題) 45.4 head 中的常用標簽 45.4.1 title 標記 45.4.2 meta 標記 45.4.3 45.4.4 45.4.4(面試題)總結: 45…