最佳數據結構來存儲標記和學生

的行列我有個同學的相應標記以下信息，位居最佳數據結構來存儲標記和學生

Name Marks Rank 
A  30  1 
B  20  2 
C  10  3

學生的排名是成反比學生的痕跡。我必須找到最好的數據結構來存儲上述信息，以便以最佳方式執行以下操作（最佳時間複雜度）。可以假定學生姓名是唯一的。

鑑於學生姓名，找到標記和排名
鑑於排名，發現一個學生的學生
更新標記的商標和名稱。

我想爲學生使用兩個hashmaps一個，並標記映射，另一個用於學生名稱和等級映射。是否有更好的數據結構？有沒有一種方法可以利用排名與標記成反比的事實。

來源

2015-06-24 poorvankBhatia

包含HashMap的（平均）O（1）操作，你所尋找的，所以你不能擊敗。但是，他們需要空間。你可以做的是：創建一個名稱，標記（？一個或多個），等級的班級。然後兩個名字和級別的hashmaps指向該用戶的類。昂貴但有效。 – EsseTi

另一種選擇是擁有一個可比較的Name + Marks類，一個按等級自動排序的比較方法，以及一個簡單的List來存儲它們。優點：更新排名是自動的，更少的空間需求，代碼可能更容易閱讀。缺點：比hashmaps慢，訪問不是o（1）了。 – Joel

爲什麼不使用帶'name'和'marks'字段的'class Student'並通過'marks'反向排列學生列表來獲得排名？您還可以添加每次列表排序時重置的屬性「rank」。 –

這可以通過兩種數據結構來完成：

一個哈希映射，從學生的名字映射到他的品位。
安order statistic tree的學生，其中比較的關鍵是成績。

這允許你做以下所有操作都必須在O(logn)：

查找學生的排名：發現它在散列圖，然後找到其訂單統計（等級）的那個樹。
更新學生成績：在地圖中找到他的舊成績，將其從地圖和樹中移除，並將其重新插入新值。
給定排名，使用順序統計樹查找相關學生及其成績。

另外，僅使用散列圖，在O(1)（平均情況）中完成學生的成績。

注：

您可以切換實現學生的名字 - >等級圖的一棵樹地圖，而不是哈希表，不影響複雜太多，並保證更好的最壞情況下的行爲。（找到一個等級也將是O（logn）而不是O（1））。

來源

2015-06-24 10:01:41 amit

我的建議也是使用兩個HashMap，但其中一個逐漸填滿，而不是增加它的排序複雜性來更新時間。這將提供以下屬性：

快速閱讀byStudent
更新較慢O（N）。如果更新很多，可以考慮將reorder從addOrUpdate方法中刪除，批量更新並在每批次之後從外部調用重新排序。
最終快速byRank閱讀。

class MyClass { 
    Comparator<RankedStudent> comp = Comparator.comparingInt(e -> e.marks); 
    private Map<String, RankedStudent> repo = new HashMap<>(); 
    private Map<Integer, RankedStudent> rankCache = new HashMap<>(); 

    public RankedStudent getByStudent(String student) { 
     return repo.get(student); 
    } 

    public RankedStudent getByRank(Integer rank) { 
     return Optional.ofNullable(rankCache.get(rank)).orElseGet(() -> { 
      rankCache.putIfAbsent(rank, repo.values().stream().sorted((s1, s2) -> rank == s1.rank ? 1 : 0) 
        .findFirst().orElse(null)); 
      return rankCache.get(rank); 
     }); 
    } 

    public void addOrUpdate(String student, Integer marks) { 
     repo.put(student, new RankedStudent(student, marks, -1)); 
     reorder(); 
    } 

    public void reorder() { 
     final Iterator<RankedStudent> it = repo.values().stream().sorted(comp.reversed()).iterator(); 
     IntStream.range(0, repo.size()).boxed().forEach(i -> it.next().rank = i + 1); 
     rankCache.clear(); 
    } 
} 

class RankedStudent { 

    public String name; 
    public int marks; 
    public int rank; 

    public RankedStudent(String name, int marks, int rank) { 
     this.name = name; 
     this.marks = marks; 
     this.rank = rank; 
    } 
}

來源

2015-06-24 12:24:56 rompetroll

最佳數據結構來存儲標記和學生

回答

相關問題