Part (a)
// 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();
while(iter.hasNext())
{
Set ballot = (Set)iter.next();
Iterator ballotIter = ballot.iterator(); 2
while (ballotIter.hasNext())
{
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
}
}
}
Notes:
- We could use a
TreeMap as well.
- The outer loop iterates over all the ballots in
ballotList ;
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.
If candidate is already in the map,
the value associated with it is replaced.
Part (b)
// 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();
while(iter.hasNext())
{
Object candidate = iter.next();
Integer count = (Integer)voteCount.get(candidate);
if (count.equals(maxCount)) 2
bestCandidates.add(candidate);
}
return bestCandidates;
}
Notes:
- You could pick
TreeSet , but then Part(c)
would become more difficult.
- Not
if (count == maxCount)...
because you are comparing Integer objects.
You could use
int maxCount = maxVotes().intValue();
...
int count = ((Integer)voteCount.get(candidate)).intValue();
if (count == maxCount) ...
but it is more error-prone.
Part (c)
O(C).
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 bestCandidates . 1
Since voteCounts is a HashMap ,
the time for traversing it in the
maxVotes method and in the candidatesWithMost
method is O(C). 2
Since bestCandidates is a HashSet ,
The time for inserting a candidate into it is O(1).
The total time is O(C). 3
Notes:
- 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.
- If
voteCounts were a TreeMap , we'd have
to multiply the traversal time by log C, because
each get(...) call takes O(log C)
time.
(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 bestCandidates a HashSet ,
so that adding a value to is always O(1).
For a TreeSet , the total worst-case time
(when all the candidates have the same count)
would be O(C log C)
|