从按字母顺序排列的列表中查找以给定字母表开头的第一个单词的索引

Question

基于当前的实现，我将从某个来源获得一个数组列表，其中包含大约1000个按字母排序的唯一名称（A-Z或Z-A）。

我需要找到以给定字母表开头的第一个单词的索引。

因此，更准确地说，当我选择一个字母表，例如“M”时，它应该给我排序列表中以“M”开头的单词第一次出现的索引。

这样我就可以找到26个字母中每个字母开头的所有单词的索引。

请帮我找到一个不影响速度的解决方案。

更新时间：

实际上，在获得1000个唯一名称后，排序也由我的一个逻辑完成<如果这可以在排序时完成，我可以避免在排序后在列表上重复查找字母的索引。

这可能吗？

谢谢，森

Answer 1

所以我想出了自己的解决方案。

package test.binarySearch;

import java.util.Random;

/**
 *
 * Binary search to find the index of the first starting in an alphabet 
 * 
 * @author Navaneeth Sen <[e-mail]>
 */
class SortedWordArray
{

    private final String[] a;                 // ref to array a
    private int nElems;               // number of data items

    public SortedWordArray(int max)          // constructor
    {
        a = new String[max];             // create array
        nElems = 0;
    }

    public int size()
    {
        return nElems;
    }

    public int find(String searchKey)
    {
        return recFind(searchKey, 0, nElems - 1);
    }

    String array = null;
    int arrayIndex = 0;

    private int recFind(String searchKey, int lowerBound,
            int upperBound)
    {
        int curIn;

        curIn = (lowerBound + upperBound) / 2;
        if (a[curIn].startsWith(searchKey))
        {
            array = a[curIn];
            if ((curIn == 0) || !a[curIn - 1].startsWith(searchKey))
            {
                return curIn;              // found it
            }
            else
            {
                return recFind(searchKey, lowerBound, curIn - 1);
            }
        }
        else if (lowerBound > upperBound)
        {
            return -1;             // can't find it
        }
        else                          // divide range
        {
            if (a[curIn].compareTo(searchKey) < 0)
            {
                return recFind(searchKey, curIn + 1, upperBound);
            }
            else                       // it's in lower half
            {
                return recFind(searchKey, lowerBound, curIn - 1);
            }
        }  // end else divide range
    }  // end recFind()

    public void insert(String value)    // put element into array
    {
        int j;
        for (j = 0; j < nElems; j++)        // find where it goes
        {
            if (a[j].compareTo(value) > 0)            // (linear search)
            {
                break;
            }
        }
        for (int k = nElems; k > j; k--)    // move bigger ones up
        {
            a[k] = a[k - 1];
        }
        a[j] = value;                  // insert it
        nElems++;                      // increment size
    }  // end insert()

    public void display()             // displays array contents
    {
        for (int j = 0; j < nElems; j++)       // for each element,
        {
            System.out.print(a[j] + " ");  // display it
        }
        System.out.println("");
    }
}  // end class OrdArray

class BinarySearchWordApp
{

    static final String AB = "12345aqwertyjklzxcvbnm";
    static Random rnd = new Random();

    public static String randomString(int len)
    {
        StringBuilder sb = new StringBuilder(len);
        for (int i = 0; i < len; i++)
        {
            sb.append(AB.charAt(rnd.nextInt(AB.length())));
        }
        return sb.toString();
    }

    public static void main(String[] args)
    {
        int maxSize = 100000;             // array size
        SortedWordArray arr;                  // reference to array
        int[] indices = new int[27];
        arr = new SortedWordArray(maxSize);   // create the array

        for (int i = 0; i < 100000; i++)
        {
            arr.insert(randomString(10));   //insert it into the array
        }

        arr.display();                 // display array
        String searchKey;
        for (int i = 97; i < 124; i++)
        {
            searchKey = (i == 123)?"1":Character.toString((char) i);

            long time_1 = System.currentTimeMillis();
            int result = arr.find(searchKey);
            long time_2 = System.currentTimeMillis() - time_1;
            if (result != -1)
            {
                indices[i - 97] = result;
                System.out.println("Found " + result + "in "+ time_2 +" ms");
            }
            else
            {
                if (!(i == 97))
                {
                    indices[i - 97] = indices[i - 97 - 1];
                }

                System.out.println("Can't find " + searchKey);
            }
        }

        for (int i = 0; i < indices.length; i++)
        {
            System.out.println("Index [" + i + "][" + (char)(i+97)+"] = " + indices[i]);
        }
    }  // end main()

} 

欢迎所有评论。

Answer 2

我希望这段代码能对您有所帮助。我猜这个问题与Java有关，因为您提到了ArrayList。

String[] unsorted = {"eve", "bob", "adam", "mike", "monica", "Mia", "marta", "pete", "Sandra"};
    ArrayList<String> names = new ArrayList<String>(Arrays.asList(unsorted));

    String letter = "M"; // find index of this

     class MyComp implements Comparator<String>{
        String first = "";
        String letter;

        MyComp(String letter){
            this.letter = letter.toUpperCase();
        }

        public String getFirst(){
            return first;
        }

        @Override
        public int compare(String s0, String s1) {

            if(s0.toUpperCase().startsWith(letter)){
                if(s0.compareTo(first) == -1 || first.equals("")){
                    first = s0;
                }
            }

            return s0.toUpperCase().compareTo(s1.toUpperCase());
        }

    };

    MyComp mc = new MyComp(letter);

    Collections.sort(names, mc);

    int index = names.indexOf(mc.getFirst()); // the index of first name starting with letter

我不确定是否可以将名字的索引存储在比较器中而没有太多开销。无论如何，如果您实现了自己版本的排序算法，例如快速排序，您应该了解元素的索引，并且可以在排序时计算索引。这取决于您选择的排序算法和实现。事实上，如果我知道您的排序是如何实现的，我们可以插入索引计算。