Java C++ 題解leetcode857雇傭K名工人最低成本vector pair
題目要求
思路:優(yōu)先隊(duì)列 + 貪心
Java
class Solution { public double mincostToHireWorkers(int[] quality, int[] wage, int k) { int n = quality.length; double[][] ratio = new double[n][2]; for (int i = 0; i < n; i++) { ratio[i][0] = wage[i] * 1.0 / quality[i]; ratio[i][1] = quality[i] * 1.0; } Arrays.sort(ratio, (a, b) -> Double.compare(a[0], b[0])); PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); double res = 1e18; for (int i = 0, tot = 0; i < n; i++) { int cur = (int) ratio[i][1]; tot += cur; pq.add(cur); if (pq.size() > k) tot -= pq.poll(); if (pq.size() == k) res = Math.min(res, tot * ratio[i][0]); } return res; } }
- 時(shí)間復(fù)雜度:O(n log ?n)
- 空間復(fù)雜度:O(n)
C++
學(xué)習(xí)了一下vector
和pair
的相互套用,以及自定義排序等內(nèi)容。
class Solution { public: double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) { int n = quality.size(); vector<pair<double, int>> ratio; for (int i = 0; i < n; i++) { ratio.emplace_back(wage[i] * 1.0 / quality[i], quality[i]); } sort(ratio.begin(), ratio.end(), [](const pair<double, int> &a, const pair<double, int> &b) { return a.first < b.first; }); priority_queue<int> pq; double res = 1e18; for (int i = 0, tot = 0; i < n; i++) { int cur = ratio[i].second; tot += cur; pq.emplace(cur); if (pq.size() > k) { tot -= pq.top(); pq.pop(); } if (pq.size() == k) res = min(res, tot * ratio[i].first); } return res; } };
- 時(shí)間復(fù)雜度:O(n log ?n)
- 空間復(fù)雜度:O(n)
Rust
use std::collections::BinaryHeap; impl Solution { pub fn mincost_to_hire_workers(quality: Vec<i32>, wage: Vec<i32>, k: i32) -> f64 { let (mut res, mut tot, mut pq) = (f64::MAX, 0, BinaryHeap::new()); let mut ratio = quality.iter().zip(wage.iter()).map(|(q, w)| (*w as f64 / *q as f64, *q as f64)).collect::<Vec<_>>(); ratio.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap()); for (a, b) in ratio { tot += b as i32; pq.push(b as i32); if pq.len() as i32 > k { tot -= pq.pop().unwrap(); } if pq.len() as i32 == k { res = res.min(a * tot as f64); } } res } }
- 時(shí)間復(fù)雜度:O(n log? n)
- 空間復(fù)雜度:O(n)
以上就是Java C++ 題解leetcode857雇傭K名工人最低成本vector pair的詳細(xì)內(nèi)容,更多關(guān)于Java C++ vector pair的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C語言中g(shù)etchar的用法以及實(shí)例解析
getchar()是stdio.h中的庫函數(shù),它的作用是從stdin流中讀入一個(gè)字符,下面這篇文章主要給大家介紹了關(guān)于C語言中g(shù)etchar的用法以及實(shí)例的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-03-03c/c++拷貝構(gòu)造函數(shù)和關(guān)鍵字explicit詳解
這篇文章主要介紹了c/c++拷貝構(gòu)造函數(shù)和關(guān)鍵字explicit的相關(guān)知識,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-08-08C語言實(shí)現(xiàn)飛機(jī)訂票系統(tǒng)的完整代碼
為了免去在窗口排隊(duì)買票的麻煩,飛機(jī)訂票系統(tǒng)應(yīng)運(yùn)而生,下面這篇文章主要給大家介紹了關(guān)于C語言實(shí)現(xiàn)飛機(jī)訂票系統(tǒng)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06C++利用Socket實(shí)現(xiàn)主機(jī)間的UDP/TCP通信
這篇文章主要為大家詳細(xì)介紹了C++如何利用Socket實(shí)現(xiàn)主機(jī)間的UDP/TCP通信功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2023-01-01VS2019開發(fā)簡單的C/C++動(dòng)態(tài)鏈接庫并進(jìn)行調(diào)用的實(shí)現(xiàn)
這篇文章主要介紹了VS2019開發(fā)簡單的C/C++動(dòng)態(tài)鏈接庫并進(jìn)行調(diào)用的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03