查找字符串‘置换’基于字母顺序

Question

我想请教，如果没有找到一个字符串的一个更有效的方法根据其字母顺序排列上，像下面我的代码。 我用绳子长达16个字符，并且数据量巨大的工作，并运行我的程序需要太多的时间和内存。

问题的基本表示

输入：拼音

输出：16752348

所以在单词“字母”字母“A”是字母表中的第一个，它标记索引1，然后是另一“a”的第五位置，将其标记2，然后是“b”在第六位置时，将其标记3等..

在我不使用数字作为索引的代码，而不是的，我使用字符，所以从ASCII值的值65开始。 （因为我使用测试长字符串，但它不会改变主要目的）。所以我的程序的输出将是

输入：拼音

输出：AFGEBCDH

public static String perm(String word){ 

    char[] perm = new char[word.length()]; 
    char[] wordArray = word.toCharArray(); 
    char[] sortedWord = new char[word.length()]; 

    sortedWord = word.toCharArray(); 
    Arrays.sort(sortedWord); 

    for (int i=0; i<word.length(); i++){ 
     for (int j=0; j<word.length(); j++){ 

      if (sortedWord[i] == wordArray[j]){ 
       perm[j] = (char)(65+i); //from A 
       wordArray[j] = '.'; 

       j = word.length(); //in case, if the word has more of the tested char, we jump to the end of the cycle 
      } 
     } 
    } 

    return String.valueOf(perm); 
} 

public static void main (String [] args){ 
    System.out.println(perm("alphabet")); 
} 

Answer 1

我看着先前的溶液中，并且它出现Arrays.sort（）进行的比较的阵列需要相当长比原始类型的数组。 我尝试了多种方法，下面是给了较小的时间为大量的单词之一：

public static String perm(String word){ 
    int l = word.length(); 
    int[] els = new int[l]; 
    for (int i=0; i<l; i++) { 
     els[i] = (word.charAt(i) << 16) | i; 
    } 
    Arrays.sort(els); 
    char[] sb = new char[l]; 
    for (int i=0; i<els.length; i++) { 
     sb[i] = (char)('A' + els[i] & 0xFFFF); 
    } 
    return String.valueOf(sb); 
    } 

注意，该方法使得隐含假设的话只能使用的低15位UTF-16编码（英文字母表中的单词为真）。

在内存的利用率方面，你必须要小心一点你在Java中衡量的东西。内存利用率可能会在一种方法与另一种方法中激增的事实并不一定是一个好的指标，因为内存可能会被垃圾收集。这里的所有方法都使用临时数组/对象，它们在执行perm（）之后可用于垃圾回收（除了返回的字符串）。现在，如果你关心减少内存利用率以减少垃圾回收（并因此提高性能），我怀疑最后这种方法应该会给出好的结果，尽管我还没有对此进行评估。

Answer 2

WRT内存利用率，您粘贴程序将没有多大用处。你在做真正的代码中返回的字符串是什么？

至于性能也越高，这应该是一个好一点：

import java.util.Arrays; 

class El implements Comparable<El>{ 
char c; 
int idx; 

public El(char c, int idx) { 
    this.c = c; 
    this.idx = idx; 
} 

public int compareTo(El other) { 
    return Character.compare(c, other.c); 
} 
} 

public class Perm { 
    public static String perm(String word){ 
    int l = word.length(); 
    El[] els = new El[l]; 
    for (int i=0; i<l; i++) { 
     els[i] = new El(word.charAt(i), i); 
    } 
    Arrays.sort(els); 
    StringBuilder sb = new StringBuilder(l); 
    for (int i=0; i<els.length; i++) { 
     sb.append((char)('A' + els[i].idx)); 
    } 
    return sb.toString(); 
    } 

    public static void main (String [] args){ 
    System.out.println(perm("alphabet")); 
    } 
} 

Answer 3

试试这个：

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collections; 
import java.util.List; 

public class alphabet { 
    public static List<CharIndexHolder> charlist = new ArrayList<CharIndexHolder>(); 

    public static String perm(String word) { 
     char[] perm = new char[word.length()]; 
     char[] wordArray = word.toCharArray(); 
     char[] sortedWord = new char[word.length()]; 

     sortedWord = word.toCharArray(); 
     Arrays.sort(sortedWord); 

     for (int i=0; i<word.length(); i++){ 
      for (int j=0; j<word.length(); j++){ 

       if (sortedWord[i] == wordArray[j]){ 
        perm[j] = (char)(65+i); //from A 
        wordArray[j] = '.'; 

        j = word.length(); //in case, if the word has more of the tested char, we jump to the end of the cycle 
       } 
      } 
     } 
     return String.valueOf(perm); 
    } 

    public static String perm2(String word) { 
     charlist.clear(); 
     for(int i = 0; i < word.length(); i++) { 
      charlist.add(new CharIndexHolder(word.charAt(i), i)); 
     } 
     Collections.sort(charlist); 
     for(int i = 0; i < charlist.size(); i++) { 
      charlist.get(i).assignedindex = i; 
     } 
     char[] result = new char[word.length()]; 
     for(int i = 0; i < result.length; i++) { 
      CharIndexHolder cur = charlist.get(i); 
      result[cur.index] =(char) (charlist.get(i).assignedindex + 65); 
     } 
     return new String(result); 
    } 

    public static void main (String [] args){ 
     System.out.println(perm("alphabet")); 
     System.out.println(perm2("alphabet")); 
    } 
} 

Helper类：

public class CharIndexHolder implements Comparable<CharIndexHolder> { 
    public int index; 
    private char character; 
    public int assignedindex; 

    CharIndexHolder(Character character, int index) { 
     this.character = character; 
     this.index = index; 
    } 

    @Override 
    public int compareTo(CharIndexHolder o) { 
     if(this.character < o.character) { 
      return -1; 
     } 
     if(this.character > o.character) { 
      return 1; 
     } 
     if(this.index < o.index) { 
      return -1; 
     } 
     if(this.index > o.index) { 
      return 1; 
     } 
     return 0; 
    }  
} 

我想不出一种比N * log（n）更快的方法。如果您需要更多速度，请尝试用长数组替换列表，但每个批次只能分配一次数组（每次调用一次）。