基于資料結構解決以下問題的最佳方法-有解無憂

我最近在一次采訪中被問到這個問題。

以下是候選人和他們獲得投票的時間。

Q. 給定一個時間，列印直到那個時間獲勝的人。

坎德。時間

乙 10

C 15

C 18

C 21

乙 35

B 40

B 42

例如，在上面的 Qsn 中，如果我們被要求在 20 時刻找到獲勝者，答案將是 C -> 因為 C 有 2 票。

嘗試過的解決方案

有一個 Map<String, List> 來存盤 Map<Candidate, [Time, votes]>

我們可以遍歷陣列并僅獲取小于 20 的時間（根據問題）。

但我相信會有更優化的方法來解決這類問題。本質上將給定的資料存盤在適當的資料結構中，這將在最佳時間為我們提供結果。

謝謝

uj5u.com熱心網友回復：

我會做如下：

首先，實作一個幼稚的解決方案，比如你想到的那個，或者上面Pp88建議的那個。
然后，立即為它撰寫一個測驗，顯示⁽¹⁾它有效。
然后，實施更優化的解決方案，例如下面的解決方案。
最后，重新使用之前的測驗來證明⁽¹⁾更優的解決方案也有效。

更優化的解決方案可能如下：

構建一個LinkedHashMap，其中key為時間坐標，value為另外一張map，其中key為所有候選人的名字，value為每個候選人在該時間坐標的累計票數。
遍歷此LinkedHashMap并創建一個新地圖，其中鍵再次是時間坐標，值是該時間坐標處獲勝候選人的姓名。扔掉之前的地圖。
構建一個ArrayList包含地圖中所有鍵的。

ArrayList完成上述所有操作后，可以通過在中執行二進制搜索以找到最接近但不超過 X 的時間坐標來回答“誰是時間 X 的贏家”型別的任何查詢，然后在地圖中查找時間坐標以找到當時獲勝的候選人的姓名。

忽略準備資料結構的開銷，每個查詢的時間復雜度等于二分查找的時間復雜度，即O(log ₂ n)。這是次線性的，所以它比 O(N) 好。

⁽¹⁾充其量，我們可以說一個測驗“表明它有效”；它不能證明什么。最準確的說法是它“有充分的理由相信它有效”，但這太長了，所以“它表明它有效”是一個不錯的選擇。

uj5u.com熱心網友回復：

這是一個 O(N) 解決方案，我假設您有輸入 2 個陣列，一個用于候選，一個用于時間。如果票數相同，誰將獲勝尚不清楚，因此在這種情況下，首先獲勝。

public Optional<Character> findCandidateWithMaxVotes(Character[] candidates, int[] times, int timeLimit) {
    Character cadidateWithMaxVotes = null;
    int max = 0, count = 0;
    Map<Character, Integer> numberOvVotesForCandidate = new HashMap<>();
    for(int i = 0; i < times.length; i  ) {
        if(times[i] <= timeLimit) {
            count = numberOvVotesForCandidate.merge(candidates[i], 1, Integer::sum);
            if(max < count) {
                max = count;
                cadidateWithMaxVotes = candidates[i];
            }
        }
    }
    return Optional.ofNullable(cadidateWithMaxVotes);
}

uj5u.com熱心網友回復：

有點不清楚我們是應該只回答一個問題（“誰是時間 20 的贏家”），還是我們應該對提供的資料進行預處理，然后回答幾個問題（“誰是時間 20 的贏家”、“誰是贏家在時間 8" 等）。

第一個問題很簡單：

// Nobody is leading before elections with 0 votes
String leader = null;
int leaderVotes = 0;

HashMap<string, Integer> ballots = new HashMap<string, Integer>();

for (int i = 0; i < candidates.length;   i) {
    // too late, don't count this vote
    if (times[i] > givenTime)
        continue;

    // number of votes 
    int current = ballots.containsKey(candidates[i]) 
      ? ballots.get(candidates[i])   1
      : 1;

    ballots.set(candidates[i], current);

    // do we have a leader change?
    //TODO: add tie breaking logic here
    if (current > leaderVotes) {
        leaderVotes = current;
        leader = candidates[i];
    }
}

// at givenTime we have leader with leaderVotes

第二個問題更棘手：

我們按時間對選票進行排序
像我們在第一個問題中一樣掃描它們
在每次領導者變更時，我們都會在(time, leader)串列中添加一條記錄
完成所有這些后，我們就有了一個已準備好進行二分搜索的排序串列：因為我們正在尋找不遲于的最新記錄。timetime

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532380.html

標籤：爪哇算法数据结构哈希图

上一篇：河內拼圖禁止移動

下一篇：ASF掛卡