家庭作業問題

Question

有效的算法我需要分析的是滿足下列問題文本：

生成的輸出，顯示多少次在文中出現的每個單詞的計數。報告應按字長排序，然後進行自然排序。

我停靠點爲我的解決方案給出下面。有更好的解決方案嗎？我沒有使用過地圖或任何收藏，因爲我們被告知，那些不使用收藏的人會得到額外的信用。

我的POJO

/** 
* An instance of this object represents the string that occurs in a sentence 
* and the number of times it occurs in a single string. 
*/ 
public class Word implements Comparable<Word> { 
    private final String word; 
    private int counter = 1; 

    public Word(String word) { 
    this.word = word; 
    } 

    public void incrementCounter() { 
    this.counter ++; 
    } 

    public String getWord() { 
    return word; 
    } 

    public int getCounter() { 
    return counter; 
    } 

    /** 
    * Overrides the default hashcode function. 
    */ 
    @Override 
    public int hashCode() { 
    int hashCode = 103034; 
    hashCode += this.word != null ? this.word.hashCode()^3 : 0; 
    hashCode += this.counter^2; 
    return hashCode; 
    } 

/** 
    * Overrides the default equals function. 
    */ 
@Override 
public boolean equals(Object obj) { 
    if (obj == null) { 
    return false; 
    } 
    if (this == obj) { 
    return true; 
    } 
    if (!(obj instanceof Word)) { 
    return false; 
    } 
    Word otherWord = (Word) obj; 
    if (this.word != null && this.word.equals(otherWord.getWord())) { 
    return true; 
    } 
    return false; 
} 

    @Override 
    public String toString() { 
    final StringBuilder sb = new StringBuilder(); 
    sb.append("Word"); 
    sb.append("{word='").append(word).append('\''); 
    sb.append(", counter=").append(counter); 
    sb.append('}'); 
    return sb.toString(); 
    } 


/** 
* The implementation checks for the order of comparison. 
* The implementation first compares by presence of word string. 
* 
* @param w Word to be compared 
* @return calculated order of comparison. 
*/ 
@Override 
public int compareTo(Word w) { 
    if (w == null) { 
    return -1; 
    } 
    if (this.word == null && w.getWord() != null) { 
    return 1; 
    } 
    if (this.word != null && w.getWord() == null) { 
    return -1; 
    } 
    return StringUtils.compareString(this.word, w.getWord()); 
} 
} 

---

import java.util.Comparator; 

/** 
* An instance of this class is responsible for comparing the instances of two word 
* instances by comparing against the word string. 
*/ 
public class WordComparator implements Comparator<Word> { 

    /** 
    * Compares two instances of words first by length of the word string and then by the 
    * word itself. 
    * 
    * @param firstWord first word to be compared 
    * @param secondWord second word to be compared 
    * @return negative number if the first word is less than the second word; 
    *  positive if the first word is greater than the second word; 0 if equal. 
    */ 
    @Override 
    public int compare(Word firstWord, Word secondWord) { 
    if (firstWord == secondWord) { 
     return 0; 
    } 
    if (firstWord != null && secondWord == null) { 
     return -1; 
    } 
    if (firstWord == null && secondWord != null) { 
     return 1; 
    } 
    return StringUtils.compareString(firstWord.getWord(), secondWord.getWord()); 
    } 
} 

---

實用工具類。

public class StringUtils { 

    // Not to be instantiated. 
    private StringUtils() {} 

    /** 
    * Compares the string first by word length and then by string. 
    * 
    * @param first First string to be compared. 
    * @param second Second string to be compared 
    * @return integer representing the output of comparison. 
    */ 
    public static int compareString(String first, String second) { 
    if (first == second) { 
     return 0; 
    } 
    if (first == null && second != null) { 
     return 1; 
    } 
    if (first != null && second == null) { 
     return -1; 
    } 
    int wordLengthDifference = first.length() - second.length(); 
    if (wordLengthDifference == 0) { 
     return first.compareTo(second); 
    } 
    return wordLengthDifference; 
    } 
} 

---

主要方法：

import java.util.Arrays; 
import java.util.Collections; 
import java.util.Comparator; 

/** 
* Finds the number of occurrences of word a in given string. The implementation expects 
* the input to be passed adsingle string argument. 
*/ 
public class StringWordOccurences { 

    /** 
    * Finds the number of occurrences of a word in a string. The implementation relies 
    * on the following assumptions. 
    * 
    * <p>The word is passed as separate strings as in {@code "Hello" "World"} instead of 
    * a single string {@code "Hello World"}. 
    * 
    * @param args Arguments to be sorted by first word length and then by string. 
    */ 
    public static void main(String[] args) { 
    if (args == null || args.length == 0) { 
     System.out.println("There were no words. The count is 0"); 
     return; 
    } 

    // Find the number of unique words and put them in an array. 
    Comparator<Word> wordComparator = new WordComparator(); 
    Arrays.sort(args, new Comparator<String>() { 
     @Override 
     public int compare(String first, String second) { 
     return StringUtils.compareString(first, second); 
     } 
    }); 

    Word [] words = new Word[args.length]; 
    int numberOfUniqueWords = 0; 
    for (String wordAsString : args) { 
     Word word = new Word(wordAsString); 
     int index = Arrays.binarySearch(words, word, wordComparator); 
     if (index > -1) { 
     words[index].incrementCounter(); 
     } else { 
     words[numberOfUniqueWords ++] = word; 
     } 
    } 
    Word [] filteredWords = Arrays.copyOf(words, numberOfUniqueWords); 
    // The display output. 
    for (Word word : filteredWords) { 
     System.out.println(word); 
     } 
    } 
} 

Answer 1

你不需要二進制搜索您所期望的順序排序你的話後，因爲相同的話會彼此相鄰。只需查看所有單詞並將其與前一個單詞進行比較即可。如果它們相等，則增加計數器。如果不相等，則可以立即打印完成的前一個單詞的結果（無需將結果存儲在數組中）。你也不需要Word類，你可以用Strings來完成。

Answer 2

我能想到的，但顯然這些都是第二猜測的幾點...

1. 你有3個地方有這樣做的話比較相似的邏輯。
2. 溝渠Arrays.sort，Arrays.binarySearch和Arrays.copyOf。不要在搜索自己 - 可能是簡單
3. 其實你可以排序你已經減少到唯一值