java - 作业问题的有效算法

Question

我需要分析满足以下问题的文本:

Generate an output that shows a count of how many times each word occurs in the text. The report should be sorted first by word length, followed a natural sort.

我的解决方案被停靠点如下。有更好的解决方案吗？我没有使用 map 或任何 Collection ，因为我们被告知那些不使用 Collection 的人将获得额外的积分。

我的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 来完成。