实现字符串计数排序时遇到问题。

huangapple go评论46阅读模式
英文:

trouble implementing counting sort for strings

问题

以下是您提供的内容的翻译:

我尝试根据字符串中的第二个字符对其进行排序时出现了这个错误,但当我使用第一个字符时,它正常运行。

在线程 "main" 中出现异常:java.lang.ArrayIndexOutOfBoundsException:索引 -1 超出范围,长度为 8
在 StringCountSort.java 的第 27 行
在 StringCountSort.java 的第 38 行

import java.util.Arrays;

public class StringCountSort {
    
    public static void countingSort(String[] array, int size, int digit)
    {

        String[] result = new String[size+1];
        
        int maximum = 122;
        
        int[] count = new int[maximum + 1];
        for (int i = 0; i < count.length; i++){
            count[i] = 0;
        }
        
        for (int i = 0; i < size; i++){
            count[array[i].charAt(digit)] +=1;
        }
        
        for (int i = 1; i < count.length; i++){
            count[i] += count[i-1];
        }
    
        for (int i = size -1; i >= 0; i--){

            result[count[array[i].charAt(digit)] - 1] = array[i];
            count[array[i].charAt(0)]--;
        }

        for (int i = 0; i < size; i++) {
            array[i] = result[i];
        }
    }
    
    public static void main(String args[]){
        String[] data = { "eg", "fa", "bz", "ch", "hv", "df", "ag" };
        StringCountSort.countingSort(data, data.length, 1);
        System.out.println("按升序排序的排序后数组:");
        System.out.println(Arrays.toString(data));
        
    }
}
第 28 行 result[count[array[i].charAt(digit)] - 1] = array[i];
第 37 行 StringCountSort.countingSort(data, data.length, 1);
英文:

I get this error when I attempt to sort it based off the second char in the string but it runs
fine when I use the first char

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 8
at StringCountSort.countingSort(StringCountSort.java:27)
at StringCountSort.main(StringCountSort.java:38)

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-html -->

import java.util.Arrays;
public class StringCountSort{
public static void countingSort(String[] array, int size, int digit)
{
String[] result = new String[size+1];
int maximum = 122;
int[] count = new int[maximum + 1];
for (int i = 0; i &lt; count.length; i++){
count[i] = 0;
}
for (int i = 0; i &lt; size; i++){
count[array[i].charAt(digit)] +=1;
}
for (int i = 1; i &lt; count.length; i++){
count[i] += count[i-1];
}
for (int i = size -1; i &gt;= 0; i--){
result[count[array[i].charAt(digit)] - 1] = array[i];
count[array[i].charAt(0)]--;
}
for (int i = 0; i &lt; size; i++) {
array[i] = result[i];
}
}
public static void main(String args[]){
String[] data = { &quot;eg&quot;, &quot;fa&quot;, &quot;bz&quot;, &quot;ch&quot;, &quot;hv&quot;, &quot;df&quot;, &quot;ag&quot; };
StringCountSort.countingSort(data, data.length, 1);
System.out.println(&quot;Sorted Array in Ascending Order: &quot;);
System.out.println(Arrays.toString(data));
}
}

<!-- end snippet -->

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-html -->

line 28 result[count[array[i].charAt(digit)] - 1] = array[i]; 
line 37 StringCountSort.countingSort(data, data.length, 1); 

<!-- end snippet -->

答案1

得分: 1

将以下部分翻译为中文:

count[array[i].charAt(0)]--;

翻译为:

count[array[i].charAt(digit)]--;

这样就可以解决问题。

我还建议进行以下改进:

  1. 你不需要将array的长度作为参数传递。
  2. 你不需要将count的每个int都设置为0
  3. maximum应该是Character.MAX_VALUE,以支持所有可能的字符。

最终的函数可以看起来像这样:

public static void countingSort(String[] array, int digit) {
    String[] result = new String[array.length];
    int[] count = new int[Character.MAX_VALUE + 1];

    for (int i = 0; i < array.length; i++){
        count[array[i].charAt(digit)]++;
    }
    for (int i = 1; i < count.length; i++){
        count[i] += count[i-1];
    }
    for (int i = array.length -1; i >= 0; i--){
        result[count[array[i].charAt(digit)] - 1] = array[i];
        count[array[i].charAt(digit)]--;
    }
    for (int i = 0; i < array.length; i++) {
        array[i] = result[i];
    }
}
英文:

Change

count[array[i].charAt(0)]--;

to

count[array[i].charAt(digit)]--;

This should do the trick.

I also suggest the following improvements:

  1. You don't need to pass the length of array as an argument.
  2. You don't need to set every int of count to 0;
  3. maximum should be Character.MAX_VALUE, to support every possible character.

The finished function could look like this:

    public static void countingSort(String[] array, int digit) {
String[] result = new String[array.length];
int[] count = new int[Character.MAX_VALUE + 1];
for (int i = 0; i &lt; array.length; i++){
count[array[i].charAt(digit)]++;
}
for (int i = 1; i &lt; count.length; i++){
count[i] += count[i-1];
}
for (int i = array.length -1; i &gt;= 0; i--){
result[count[array[i].charAt(digit)] - 1] = array[i];
count[array[i].charAt(digit)]--;
}
for (int i = 0; i &lt; array.length; i++) {
array[i] = result[i];
}
}

答案2

得分: 0

Here are the translations:

  1. count[array[i].charAt(digit)] +=1 更改为 count[array[i].charAt(0)] +=1
  2. result[count[array[i].charAt(digit)] - 1] = array[i]; count[array[i].charAt(0)]--; 更改为 result[--count[array[i].charAt(0)]] = array[i];

如果要根据第二个字符对字符串进行排序,则简单更改:

  1. count[array[i].charAt(0)]--; 更改为 count[array[i].charAt(digit)]--;
英文:

Things that need to be changed are (if you want to sort the strings on the basis of first character)

  1. count[array[i].charAt(digit)] +=1 to count[array[i].charAt(0)] +=1
  2. result[count[array[i].charAt(digit)] - 1] = array[i]; count[array[i].charAt(0)]--; to result[--count[array[i].charAt(0)]] = array[i];

If you want to sort the string on the basis of the second character then simply change :

  1. count[array[i].charAt(0)]--; to count[array[i].charAt(digit)]--;

huangapple
  • 本文由 发表于 2020年8月2日 09:59:47
  • 转载请务必保留本文链接:https://go.coder-hub.com/63211666.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定