Address: leetcode-cn.com/problems/ra…
Title description:
There is now a special ranking system in which teams are ranked according to the order in the voter’s mind, and each voter has to rank all the participating teams from highest to lowest.
The ranking rules are as follows:
Teams are ranked according to the number of “number one” tickets they receive. If there is a tie between multiple teams, the number of “second place” tickets will continue to be considered. And so on, until there is no longer a juxtaposition. If a tie still occurs after all votes are considered, the teams are ranked alphabetically. You are given a string array of votes representing the ranking given by all the voters, and you rank all the teams according to the above ranking rules.
Return a string that represents the rank of all teams sorted by the ranking system.
Example 1:
Having input: votes = [“ABC”,”ACB”,”ABC”,”ACB”,”ACB”] Team B received two “second place” votes and three “third place” votes. Team C received three “second place” votes and two “third place” votes. Because there were more votes for team C, team C was second and team B was third. Example 2:
Votes = [“WXYZ”,”XYZW”] Output: “XWYZ” Explanation: Team X becomes the first ranked team after the tie break. Team X and Team W had the same “first place” vote, but team X had one “second place” vote, while TEAM W did not have the “second place” vote. Example 3:
Input: votes = [” ZMNAGUEDSJYLBOPHRQICWFXTVK “] output: “ZMNAGUEDSJYLBOPHRQICWFXTVK explanation:” there is only one voter, so ranking completely according to his will. Example 4:
Votes = [“BCA”,”CAB”,”CBA”,”ABC”,”ACB”,”BAC”] Output: “ABC” Explanation: Team A has two votes “first “, two votes” second “and two votes” third “. Team B received two “first place” votes, two “second place” votes and two “third place” votes. Team C received two “first place” votes, two “second place” votes and two “third place” votes. They’re all tied, so we need to rank them alphabetically. Example 5:
Having input: votes = [“M”,”M”,”M”,”M”,”M”]
Tip:
1 <= votes.length <= 1000 1 <= votes[i].length <= 26 votes[i].length == votes[j].length for 0 <= i, [j] votes[I][j] votes[I] all letters in votes[0] are unique and all letters in votes[j] also appear in votes[j], Where 1 <= j < votes.length
Analysis of the topic:
In order of the contestants, the number of votes in the first place is compared with the number of votes in the first place
Self-solving:
In order to save the number of cycles, we take such an idea, each cycle record the number of rankings.
ZUEVY votes are as follows.
The voting is as follows:
ZUEVY VYEZU EYZVU VUYZE UEZYV ZEUYV
1. In the first cycle, the first place of all voters is traversed: Z:2, V:2, E:1, U:1, Y:0
Because we have the same total number of votes, we go through the next cycle, and we look at the second place of all the voters, but it’s important to note that they only compare in the second cycle if the value of the last vote is the same.
2. It has been confirmed that Y is in the final position. VZ will compete for the top two in the second round, while EU will compete for the 34th place.
And since Y is definitely in the last place, I’m just going to ignore it, and the second round is going to be like this
V: 0, Z: 0; U: 2, E: 2,
3. The comparison of the second round also has no result, and the third round is entered.
V: 0, Z: 2; E: 2, U: 1
At this point, the comparison result is ZVEUY;
Code implementation:
private String solution1(String[] votes) {
if (votes == null || votes.length == 0 || votes[0] = =null || votes[0].length() == 0) {
return "";
}
ArrayList<OrderNode> orderList = new ArrayList<>();
int length = votes[0].length();
for (int i = 0; i < length; i++) {
orderList.add(new OrderNode(votes[0].charAt(i), 0));
}
sort(0, votes[0].length() - 1, orderList, 0, votes);
StringBuilder sb = new StringBuilder();
for (OrderNode o : orderList) {
sb.append(o.character);
}
return new String(sb);
}
/ * * *@paramStart Specifies the start coordinate * of the list to be sorted@paramEnd Specifies the end coordinate * of the list to be sorted@paramOrderList The list to be sorted *@paramPosition votes[] The number of positions in the array string *@paramVotes Indicates the string */
private void sort(int start, int end, ArrayList<OrderNode> orderList, int position, String[] votes) {
if (start >= end) {
return;
}
if (position >= votes[0].length()) {
return;
}
TreeSet<OrderNode> treeSet = new TreeSet<>(new Comparator<OrderNode>() {
@Override
public int compare(OrderNode o1, OrderNode o2) {
if (o1.value == o2.value) {
return o1.character - o2.character;
}
returno2.value - o1.value; }}); HashMap<Character, OrderNode> orderNodeHashMap =new HashMap<>();
for (int i = start; i <= end; i++) {
OrderNode orderNode = orderList.get(i);
orderNode.value = 0;
orderNodeHashMap.put(orderNode.character, orderNode);
}
for (String s : votes) {
Character character = s.charAt(position);
if (orderNodeHashMap.containsKey(character)) {
OrderNode orderNode = orderNodeHashMap.get(character);
orderNode.value++;
orderNodeHashMap.put(character, orderNode);
}
}
treeSet.addAll(orderNodeHashMap.values());
for (int i = start; i <= end; i++) {
orderList.set(i, treeSet.pollFirst());
}
int lastValue = -1;
int lastIndex = start;
int count = 0;
for (int i = start; i <= end; i++) {
OrderNode orderNode = orderList.get(i);
if(orderNode.value ! = lastValue) { sort(lastIndex, i -1, orderList, position + 1, votes);// Not equal, need to sort
lastValue = orderNode.value;
lastIndex = i;
count = 0;
} else{ count++; }}if (count > 0) {
sort(lastIndex, end, orderList, position + 1, votes);// Not equal, need to sort}}private static class OrderNode {
Character character;
// Save the total number of votes
int value = 0;
ArrayList<Integer> rank = new ArrayList<>();
public OrderNode(Character character) {
this.character = character;
}
public OrderNode(Character character, int value) {
this.character = character;
this.value = value;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof OrderNode && this.character == ((OrderNode) obj).character) {
return true;
}
return false;
}
@Override
public int hashCode(a) {
returncharacter.hashCode(); }}Copy the codeOfficial solution:
Construct a two-dimensional array to store the total number of votes for each ranking. In order to determine the ranking comparison
ZUEVY votes are as follows.
The voting is as follows:
ZUEVY VYEZU EYZVU VUYZE UEZYV ZEUYV
The structure of the two-dimensional array is as follows:
private String solution2(String[] votes) {
if (votes == null || votes.length == 0 || votes[0] = =null || votes[0].length() == 0) {
return "";
}
ArrayList<OrderNode> orderNodeArrayList = new ArrayList<>();
String allUser = votes[0];
for (int i=0; i<allUser.length(); i++){// I is the number of votes
orderNodeArrayList.add(new OrderNode(allUser.charAt(i)));
}
// Number of participants
final int userCount = votes[0].length();
for (int i=0; i<userCount; i++){// here userCount needs to be understood as ranking
for (String vote : votes) {
char c = vote.charAt(i);
int index = orderNodeArrayList.indexOf(new OrderNode(c));
OrderNode orderNode = orderNodeArrayList.get(index);
if(orderNode.rank.size() <= i){
while (orderNode.rank.size() <=i){
orderNode.rank.add( 0);
}
}
Integer integer = orderNode.rank.get(i);
orderNode.rank.set(i, integer + 1);
}
}
Collections.sort(orderNodeArrayList, new Comparator<OrderNode>() {
@Override
public int compare(OrderNode o1, OrderNode o2) {
for (int i=0; i<o1.rank.size(); i++){if(! o2.rank.get(i).equals(o1.rank.get(i))){returno2.rank.get(i) - o1.rank.get(i); }}returno1.character-o2.character; }}); StringBuilder sb =new StringBuilder();
for (OrderNode o : orderNodeArrayList) {
sb.append(o.character);
}
return new String(sb);
}
Copy the codeIt is obvious that our solution is better than the official solution. After each round of comparison, we only need to compare the same position in this ranking, while the official solution uses violence scheme to iterate all the information for comparison. Code reference address: github.com/xiaolutang/…