// precondition: each entry in ballotList is a Set representing
// one voter's ballot
// postcondition: voteCount.get(candidate) is the total number of
// times candidate appears on ballots in ballotList
public VoterBallots(List ballotList)
voteCount = new HashMap(); 1
Iterator iter = ballotList.iterator();
Set ballot = (Set)iter.next();
Iterator ballotIter = ballot.iterator(); 2
String candidate = (String)ballotIter.next();
int count = 0;
Object obj = voteCount.get(candidate);
if (obj != null)
count = ((Integer)obj).intValue();
voteCount.put(candidate, new Integer(count + 1)); 3
- We could use a
TreeMap as well.
- The outer loop iterates over all the ballots in
the inner loop iterates over all the candidates in the ballot.
Integer is immutable, so we need to create a new
Integer for the updated count and put it in the map.
candidate is already in the map,
the value associated with it is replaced.
// postcondition: returns a set containing the candidate(s)
// with the most votes
public Set candidatesWithMost()
Set bestCandidates = new HashSet(); 1
Iterator iter = voteCount.keySet().iterator();
Integer maxCount = maxVotes();
Object candidate = iter.next();
Integer count = (Integer)voteCount.get(candidate);
if (count.equals(maxCount)) 2
- You could pick
TreeSet, but then Part(c)
would become more difficult.
if (count == maxCount)...
because you are comparing
You could use
int maxCount = maxVotes().intValue();
int count = ((Integer)voteCount.get(candidate)).intValue();
if (count == maxCount) ...
but it is more error-prone.
The time of the
candidatesWithMost method consists of
the time needed to call
maxVotes, the time needed
to iterate over all the candidates (i.e., over all the keys in the
voteCount map), and the time for inserting
matching candidates into
voteCounts is a
the time for traversing it in the
maxVotes method and in the
method is O(C). 2
bestCandidates is a
The time for inserting a candidate into it is O(1).
The total time is O(C). 3
- Note that the votes have been already tallied in the constructor,
so the individual voters are no longer represented anywhere and their number V is irrelevant.
voteCounts were a
TreeMap, we'd have
to multiply the traversal time by log C, because
get(...) call takes O(log C)
(You may argue it doesn't have to in a more efficient implementation of
TreeMap traversal by keys, but there is no one to argue with
at the AP exam.
It's better to just use a
HashMap to be
on the safe side.)
- The time for inserting a candidate into
bestCandidates may potentially get you bogged down in the issue of what portion of C can match the best count, and so on.
To avoid that, make
so that adding a value to is always O(1).
TreeSet, the total worst-case time
(when all the candidates have the same count)
would be O(C log C)