2023-05-18：有 n 名工人。 給定兩個數(shù)組 quality 和 wage ， 其中，quality[i] 表示
2023-05-18：有 n 名工人。 給定兩個數(shù)組 quality 和 wage ，
其中，quality[i] 表示第 i 名工人的工作質(zhì)量，其最低期望工資為 wage[i] 。
現(xiàn)在我們想雇傭 k 名工人組成一個工資組。在雇傭 一組 k 名工人時，
我們必須按照下述規(guī)則向他們支付工資：
對工資組中的每名工人，應(yīng)當按其工作質(zhì)量與同組其他工人的工作質(zhì)量的比例來支付工資。
工資組中的每名工人至少應(yīng)當?shù)玫剿麄兊淖畹推谕べY。
給定整數(shù) k ，返回 組成滿足上述條件的付費群體所需的最小金額。
輸入： quality = [10,20,5], wage = [70,50,30], k = 2。
輸出： 105.00000。
答案2023-05-18：
解題步驟：
1.構(gòu)造 Employee 結(jié)構(gòu)體，存儲每個員工的工作質(zhì)量和垃圾系數(shù)（wage / quality）。
2.按照垃圾系數(shù)從小到大對所有員工進行排序。
3.維護一個大小為 k 的小根堆，表示當前最低期望工資組中的 k 名工人的工作質(zhì)量。
4.遍歷所有員工，如果堆未滿，則將該員工加入堆中并更新最低期望工資。如果堆已滿，則檢查當前員工能否替換堆頂元素，如果可以，則彈出堆頂元素并將當前員工入堆，更新最低期望工資。
5.最終返回最低期望工資即可。
注意事項：
??使用 golang 內(nèi)置的 container/heap 庫來實現(xiàn)小根堆。
??在比較垃圾系數(shù)大小時，需要使用小于等于號，因為可能存在兩個員工的垃圾系數(shù)完全相等的情況。
時間復(fù)雜度：排序所需的時間為 O(nlogn)，遍歷員工數(shù)組時每個員工會入堆一次，出堆一次，即共進行了 2n 次操作，而小根堆的插入和彈出操作時間復(fù)雜度均為 O(logk)，因此總時間復(fù)雜度為 O(nlogn + nlogk)。
空間復(fù)雜度：除給定數(shù)組外，我們還需要構(gòu)造 Employee 結(jié)構(gòu)體，以及維護大小為 k 的小根堆，因此需要額外使用 O(n) 空間來存儲結(jié)構(gòu)體數(shù)組，并且在堆滿時可能需要對堆進行調(diào)整，最多需要 O(k) 的額外空間。因此總空間復(fù)雜度為 O(n + k)。
go完整代碼如下：
package?main
import?(
????"container/heap"
????"fmt"
????"sort"
)
type?Employee?struct?{
????RubbishDegree?float64
????Quality???????int
}
func?NewEmployee(w,?q?int)?Employee?{
????return?Employee{RubbishDegree:?float64(w)?/?float64(q),?Quality:?q}
}
type?EmployeeHeap?[]int
func?(h?EmployeeHeap)?Len()?int????????????{?return?len(h)?}
func?(h?EmployeeHeap)?Less(i,?j?int)?bool??{?return?h[i]?>?h[j]?}
func?(h?EmployeeHeap)?Swap(i,?j?int)???????{?h[i],?h[j]?=?h[j],?h[i]?}
func?(h?*EmployeeHeap)?Push(x?interface{})?{?*h?=?append(*h,?x.(int))?}
func?(h?*EmployeeHeap)?Pop()?interface{}?{
????n?:=?len(*h)
????x?:=?(*h)[n-1]
????*h?=?(*h)[:n-1]
????return?x
}
func?min(a,?b?float64)?float64?{
????if?a?<?b?{
????????return?a
????}
????return?b
}
func?mincostToHireWorkers(quality?[]int,?wage?[]int,?k?int)?float64?{
????n?:=?len(quality)
????employees?:=?make([]Employee,?n)
????for?i?:=?range?quality?{
????????employees[i]?=?NewEmployee(wage[i],?quality[i])
????}
????sort.Slice(employees,?func(i,?j?int)?bool?{
????????return?employees[i].RubbishDegree?<=?employees[j].RubbishDegree
????})
????minTops?:=?&EmployeeHeap{}
????heap.Init(minTops)
????ans,?qualitySum?:=?1e9,?0
????for?i?:=?0;?i?<?n;?i++?{
????????curQuality?:=?employees[i].Quality
????????if?minTops.Len()?<?k?{?//?堆沒滿
????????????qualitySum?+=?curQuality
????????????heap.Push(minTops,?curQuality)
????????????if?minTops.Len()?==?k?{
????????????????ans?=?min(ans,?float64(qualitySum)*employees[i].RubbishDegree)
????????????}
????????}?else?{?//?來到當前員工的時候，堆是滿的！
????????????//?當前員工的能力，可以把堆頂干掉，自己進來！
????????????if?top?:=?(*minTops)[0];?top?>?curQuality?{
????????????????heap.Pop(minTops)
????????????????qualitySum?+=?curQuality?-?top
????????????????heap.Push(minTops,?curQuality)
????????????????ans?=?min(ans,?float64(qualitySum)*employees[i].RubbishDegree)
????????????}
????????}
????}
????return?ans
}
func?main()?{
????quality?:=?[]int{10,?20,?5}
????wage?:=?[]int{70,?50,?30}
????k?:=?2
????result?:=?mincostToHireWorkers(quality,?wage,?k)
????fmt.Println(result)
}
rust完整代碼如下：
struct?Employee?{
????rubbish_degree:?f64,
????quality:?i32,
}
impl?Employee?{
????fn?new(w:?i32,?q:?i32)?->?Self?{
????????let?rubbish_degree?=?w?as?f64?/?q?as?f64;
????????Self?{
????????????rubbish_degree,
????????????quality:?q,
????????}
????}
}
fn?mincost_to_hire_workers(quality:?Vec<i32>,?wage:?Vec<i32>,?k:?i32)?->?f64?{
????let?n?=?quality.len();
????let?mut?employees?=?Vec::with_capacity(n);
????for?i?in?0..n?{
????????employees.push(Employee::new(wage[i],?quality[i]));
????}
????//?只根據(jù)垃圾指數(shù)排序
????//?要價?/?能力
????employees.sort_by(|a,?b|?a.rubbish_degree.partial_cmp(&b.rubbish_degree).unwrap());
????//?請維持力量最小的前K個力量
????//?大根堆！門檻堆！
????let?mut?min_tops?=?std::collections::BinaryHeap::new();
????let?mut?ans?=?std::f64::MAX;
????let?mut?quality_sum?=?0;
????for?i?in?0..n?{
????????//?i?:?依次所有員工的下標
????????//?quality_sum?:?進入堆的力量總和！
????????//?cur_quality當前能力
????????let?cur_quality?=?employees[i].quality;
????????if?min_tops.len()?<?k?as?usize?{
????????????//?堆沒滿
????????????quality_sum?+=?cur_quality;
????????????min_tops.push(cur_quality);
????????????if?min_tops.len()?==?k?as?usize?{
????????????????ans?=?ans.min(quality_sum?as?f64?*?employees[i].rubbish_degree);
????????????}
????????}?else?{
????????????//?來到當前員工的時候，堆是滿的！
????????????//?當前員工的能力，可以把堆頂干掉，自己進來！
????????????if?let?Some(top)?=?min_tops.peek()?{
????????????????if?*top?>?cur_quality?{
????????????????????quality_sum?+=?cur_quality?-?min_tops.pop().unwrap();
????????????????????min_tops.push(cur_quality);
????????????????????ans?=?ans.min(quality_sum?as?f64?*?employees[i].rubbish_degree);
????????????????}
????????????}
????????}
????}
????ans
}
fn?main()?{
????let?quality?=?vec![10,?20,?5];
????let?wage?=?vec![70,?50,?30];
????let?k?=?2;
????let?result?=?mincost_to_hire_workers(quality,?wage,?k);
????println!("{}",?result);
}
c完整代碼如下：
#include?<stdio.h>
#include?<stdlib.h>
#include?<limits.h>
typedef?struct?Employee?{
????double?rubbishDegree;
????int?quality;
}?Employee;
int?cmp(const?void*?a,?const?void*?b)?{
????Employee*?pa?=?(Employee*)a;
????Employee*?pb?=?(Employee*)b;
????if?(pa->rubbishDegree?<?pb->rubbishDegree)?{
????????return?-1;
????}
????else?if?(pa->rubbishDegree?>?pb->rubbishDegree)?{
????????return?1;
????}
????else?{
????????return?0;
????}
}
double?mincostToHireWorkers(int*?quality,?int?qualitySize,?int*?wage,?int?wageSize,?int?k)?{
????int?n?=?qualitySize;
????Employee*?employees?=?(Employee*)malloc(n?*?sizeof(Employee));
????for?(int?i?=?0;?i?<?n;?i++)?{
????????employees[i].quality?=?quality[i];
????????employees[i].rubbishDegree?=?(double)wage[i]?/?(double)quality[i];
????}
????qsort(employees,?n,?sizeof(Employee),?cmp);
????int*?minTops?=?(int*)malloc(k?*?sizeof(int));
????int?topIndex?=?-1;
????double?ans?=?INT_MAX;
????int?qualitySum?=?0;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????int?curQuality?=?employees[i].quality;
????????if?(topIndex?<?k?-?1)?{
????????????qualitySum?+=?curQuality;
????????????minTops[++topIndex]?=?curQuality;
????????????if?(topIndex?==?k?-?1)?{
????????????????ans?=?qualitySum?*?employees[i].rubbishDegree;
????????????}
????????}
????????else?{
????????????if?(minTops[0]?>?curQuality)?{
????????????????qualitySum?+=?curQuality?-?minTops[0];
????????????????minTops[0]?=?curQuality;
????????????????ans?=?qualitySum?*?employees[i].rubbishDegree;
????????????????//?調(diào)整，使堆繼續(xù)保持最小堆的性質(zhì)
????????????????for?(int?j?=?0;?j?<?k?-?1;?j++)?{
????????????????????if?(minTops[j]?>?minTops[j?+?1])?{
????????????????????????int?tmp?=?minTops[j];
????????????????????????minTops[j]?=?minTops[j?+?1];
????????????????????????minTops[j?+?1]?=?tmp;
????????????????????}
????????????????????else?{
????????????????????????break;
????????????????????}
????????????????}
????????????}
????????}
????}
????free(employees);
????free(minTops);
????return?ans;
}
int?main()?{
????int?quality[]?=?{?10,20,5?};
????int?wage[]?=?{?70,50,30?};
????int?k?=?2;
????double?result?=?mincostToHireWorkers(quality,?sizeof(quality)?/?sizeof(int),?wage,?sizeof(wage)?/?sizeof(int),?k);
????printf("%lf\n",?result);?
????return?0;
}
c++完整代碼如下：
#include?<iostream>
#include?<vector>
#include?<queue>
#include?<algorithm>
#include?<limits>
using?namespace?std;
struct?Employee?{
????double?rubbishDegree;
????int?quality;
????Employee()?=?default;
????Employee(int?w,?int?q)?:?rubbishDegree(static_cast<double>(w)?/?static_cast<double>(q)),?quality(q)?{}
????bool?operator<(const?Employee&?other)?const?{
????????return?rubbishDegree?<?other.rubbishDegree;
????}
};
double?mincostToHireWorkers(vector<int>&?quality,?vector<int>&?wage,?int?k)?{
????int?n?=?quality.size();
????vector<Employee>?employees(n);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????employees[i]?=?Employee(wage[i],?quality[i]);
????}
????//?只根據(jù)垃圾指數(shù)排序
????sort(employees.begin(),?employees.end());
????//?請維持力量最小的前K個力量
????//?大根堆！門檻堆！
????priority_queue<int>?minTops;
????double?ans?=?numeric_limits<double>::max();
????for?(int?i?=?0,?qualitySum?=?0;?i?<?n;?i++)?{
????????//?i?:?依次所有員工的下標
????????//?qualitySum?:?進入堆的力量總和！
????????//?curQuality當前能力
????????int?curQuality?=?employees[i].quality;
????????if?(minTops.size()?<?k)?{?//?堆沒滿
????????????qualitySum?+=?curQuality;
????????????minTops.push(curQuality);
????????????if?(minTops.size()?==?k)?{
????????????????ans?=?min(ans,?qualitySum?*?employees[i].rubbishDegree);
????????????}
????????}
????????else?{?//?來到當前員工的時候，堆是滿的！
????????????//?當前員工的能力，可以把堆頂干掉，自己進來！
????????????if?(minTops.top()?>?curQuality)?{
????????????????//??????????????qualitySum?-=?minTops.top();
????????????????//??????????????qualitySum?+=?curQuality;
????????????????//??????????????minTops.pop();
????????????????//??????????????minTops.push(curQuality);
????????????????qualitySum?+=?curQuality?-?minTops.top();
????????????????minTops.pop();
????????????????minTops.push(curQuality);
????????????????ans?=?min(ans,?qualitySum?*?employees[i].rubbishDegree);
????????????}
????????}
????}
????return?ans;
}
int?main()?{
????vector<int>?quality?=?{?10,?20,?5?};
????vector<int>?wage?=?{?70,?50,?30?};
????int?k?=?2;
????double?result?=?mincostToHireWorkers(quality,?wage,?k);
????cout?<<?result?<<?endl;?//?105
????return?0;
}
福大大架構(gòu)師每日一題
java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。
公眾號
