Java C++ 題解leetcode857雇傭K名工人最低成本vector pair
更新時間：2022年09月14日 09:22:49 作者：AnjaVon
這篇文章主要為大家介紹了Java C++ 題解leetcode857雇傭K名工人最低成本vector pair示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
題目要求
思路：優(yōu)先隊列 + 貪心
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;
}
}
- 時間復雜度：O(n log ?n)
- 空間復雜度：O(n)
C++
學習了一下vector和pair的相互套用，以及自定義排序等內容。
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;
}
};
- 時間復雜度：O(n log ?n)
- 空間復雜度：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
}
}
- 時間復雜度：O(n log? n)
- 空間復雜度：O(n)
以上就是Java C++ 題解leetcode857雇傭K名工人最低成本vector pair的詳細內容，更多關于Java C++ vector pair的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了VC實現(xiàn)屏幕截詞功能的方法詳解,對于深入的理解windows程序運行原理很有幫助,需要的朋友可以參考下2014-07-07
這篇文章主要介紹了詳解C語言數(shù)組越界及其避免方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
這篇文章主要介紹了C++處理圖存儲的方式分享，文章圍繞鄰接矩陣、鄰接表、鏈式前向的主題展開詳細內容，具有一定的參考價值，需要的小伙伴可以參考一下2022-03-03
這篇文章主要給大家介紹了關于怎么在C++二進制文件中注入git信息的相關資料,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下2021-06-06
C++ 內存分配處理函數(shù)set_new_handler的使用
這篇文章主要介紹了C++ 內存分配處理函數(shù)set_new_handler的使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-02-02
C++ 使用CRC32檢測內存映像完整性的實現(xiàn)步驟
當我們使用動態(tài)補丁的時候，那么內存中同樣不存在校驗效果，也就無法抵御對方動態(tài)修改機器碼了，為了防止解密者直接對內存打補丁，我們需要在硬盤校驗的基礎上，增加內存校驗，防止動態(tài)補丁的運用。2021-06-06
這篇文章主要介紹了php5系列的apache遠程執(zhí)行漏洞攻擊腳本,需要的朋友可以參考下2014-06-06
異常是面向對象語言常用的一種處理錯誤的方式，當一個函數(shù)發(fā)現(xiàn)自己無法處理的錯誤時就可以拋出異常，本文我們將對C++ 異常機制進行深入剖析，感興趣的同學跟著小編一起來看看吧2023-07-07
這篇文章主要介紹了C++中取余運算的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
C語言內存的動態(tài)分配比較malloc和realloc的區(qū)別
這篇文章主要介紹了C語言內存的動態(tài)分配比較malloc和realloc的區(qū)別,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是本文的詳細內容,需要的朋友可以參考下2021-07-07