亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

合并 n 個列表并對數據進行排序,保持原始順序/約束

合并 n 個列表并對數據進行排序,保持原始順序/約束

汪汪一只貓 2022-07-06 09:44:43
我在編碼比賽中遇到了以下問題。我嘗試了很多,但是一個私人測試用例總是以錯誤的答案對我來說失敗,我無法弄清楚為什么我的下面的方法會失敗。我沒有天真的解決方案來生成壓力測試用例并進行比較。此外,不會發表社論。因此,如果可能的話,我正在尋找有人指出我的方法中的缺陷。以下是對該問題的詳細描述以及我到目前為止所嘗試的內容。問題:有多個地區,您會根據學生在各自地區的排名為每個地區的學生打分。例如:Region1:StudentName, ScoreA,           50.0B,           60.0  C,           40.0 Region2:StudentName, ScoreD,           30.0E,           10.0F,           20.0 在上面的數據中,學生 A 在 Region1 中排名 1,B 在 Region1 中排名 2,C 在 Region1 中排名 3。類似地,D 在 Region2 中有 Rank1,E 有 Rank2,F 有 Rank3。一個學生的分數可能較低,但在同一區域內的排名仍然較高。例如,A 在 Region1 中的排名比 B 好,即我們應該假設每個區域的數據已經按照排名進行了排序。我們的任務是合并所有區域的數據并創建一個根據分數排名的全局數據。約束條件是,任何在該地區排名較低的學生仍然不能比該地區其他學生的排名高于原始地區數據中的排名。例如:Region1:A, 50.0B, 60.0C, 40.0 Region2:D, 30.0E, 10.0F, 20.0將合并為:A, 50.0B, 60.0C, 40.0 D, 30.0E, 10.0F, 20.0順序沒有根據分數改變,因為 B 將始終低于 A 并且 F 將始終低于 E 根據他們所在地區的限制。其他測試用例:Region1:A, 50.0B, 60.0C, 70.0 Region2:D, 30.0E, 20.0F, 10.0再次導致 A,B,C,D,E,F 的順序Region1:A, 60.0B, 80.0C, 100.0 Region2:D, 70.0E, 90.0F, 110.0將導致:D、E、F、A、B、C但,Region1:A, 11.5B, 8.5C, 10.0 Region2:D, 12.0E, 9.0F, 9.5將導致:D, 12.0A, 11.5E, 9.0 B, 8.5C, 10.0F, 9.5Constraints:1<=number of regions<=6score can be upto 7 decimal places我的方法是將所有輸入數據添加到一個列表中并保持穩定的排序,即如果兩個學生的區域相同,則比較他們在區域中的排名,否則比較分數。static class Student implements Comparable<Student>{String name;double score;int zone;int rank;//constructorpublic int compareTo(Student o){if(this.zone == o.zone){//lower i.e. better rankreturn Integer.compare(this.rank, o.rank);}//higher i.e. better scorereturn Double.compare(o.score, this.score);}}main(){//read data from console input into an ArrayList<Student> studentsCollections.sort(students);//print each student from students}這個問題沒有提到兩個學生在不同區域的分數是否相等。在這種情況下,我嘗試使用他們各自在區域中的排名來打破平局,但私人測試用例一直失敗。我最初認為該問題可能缺少一些信息,但我在競賽儀表板中看到許多成功提交此問題的信息。這就是我相信我遺漏了一些東西的原因,這個問題并不像我想的那么簡單。但是,我無法想出一個測試用例來驗證這個假設。
查看完整描述

2 回答

?
慕尼黑5688855

TA貢獻1848條經驗 獲得超2個贊

據我了解這個問題,要求是根據分數對學生進行排序,但還有一個額外的限制是要保留一個區域內學生的相對順序。


鑒于問題中列出的示例之一的輸入數據,


Region1:

A, 11.5

B, 8.5

C, 10.0 


Region2:

D, 12.0

E, 9.0

F, 9.5

僅按分數排序會得出以下結果:DACFEB。


然而,關于在一個區域內保持相對排序的約束需要以下部分排序A < B < C 和 D < E < F。


OP 將此特定示例的解決方案稱為 DAEBCF。在對該問題的評論中,我為此示例提出了另外兩種可能的解決方案:DABCEF 和 DAEFBC。我沒有看到任何標準可以讓我們決定哪些可能的解決方案是正確的。因此,該問題受到了不足的約束。人們可以爭論這些解決方案中的哪一個比其他解決方案更可取,但這樣做會引入新的約束,而這些約束在原始問題中并不明顯。


鑒于有多個解決方案滿足問題中的所有標準,這意味著該域中的值沒有完全排序。此外,鑒于正確的比較器必須對其域的值進行總排序,因此不可能為該域編寫適當的比較器。


當然,可以編寫一個正確的比較器,它有一些行為,并且會更喜歡這些可能的解決方案之一而不是其他解決方案。這樣做將隱含地實施不屬于問題陳述的附加約束。事實上,Vincent van der Weele似乎已經這樣做了。語句“下一個空白點必須由其中一個區域的排名最高的剩余元素填充。哪個?得分最高的那個”引入了附加約束。它導致了 OP 建議的排序 DAEBCF。雖然這是明智的,但它必然是“正確”的排序。


另一種算法可能如下。1)從一個空的結果列表開始,并按排名順序維護來自每個地區的學生列表。2) 找出剩下的得分最高的學生。3) 取該學生和同一區域內排名較高的學生,并將它們附加到結果中,保持相對順序。4) 重復直到沒有學生留下。


將此算法應用于示例輸入會產生 DABCEF。這是明智的,但方式不同。同樣,我們不知道這是否是“正確”的答案。


要么是編程競賽中的問題一開始就沒有明確說明,要么是競賽的問題陳述與 Stack Overflow 上 OP 的問題之間丟失了一些信息。


查看完整回答
反對 回復 2022-07-06
?
智慧大石

TA貢獻1946條經驗 獲得超3個贊

您的比較器不正確。您基本上說,如果學生來自同一地區,則按排名排序,否則按分數排序。但事實并非如此,如本例所示:


Region1:

A, 11.5

B, 8.5

C, 10.0 


Region2:

D, 12.0

E, 9.0

F, 9.5

結果是


D, 12.0

A, 11.5

E, 9.0 

B, 8.5

C, 10.0

F, 9.5

即,得分為 9.0 的 E 排在得分為 10.0 的 C 之前,即使他們來自不同的地區。


一個更簡單的算法,它確實有效:


逐個元素填充結果。下一個空位必須由其中一個區域中排名最高的剩余元素填充。哪一個?得分最高的那個。因此,從其區域中刪除該元素,將其添加到結果中,然后重復直到完成。


查看完整回答
反對 回復 2022-07-06
  • 2 回答
  • 0 關注
  • 111 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號