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

问题描述

基于当前的实现，我将得到一个数组列表，其中包含来自某个来源的按字母顺序排序(A-Z 或 Z-A)的大约 1000 个唯一名称.

Based on the current implementation, I will get an arraylist which contains some 1000 unique names in the alphabetically sorted order(A-Z or Z-A) from some source.

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

I need to find the index of the first word starting with a given alphabet.

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

So to be more precise, when I select an alphabet, for eg. "M", it should give me the index of the first occurrence of the word starting in "M" form the sorted list.

这样我应该能够找到从 26 个字母中的每一个开始的所有第一个单词的索引.

And that way I should be able to find the index of all the first words starting in each of the 26 alphabets.

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

Please help me find a solution which doesn't compromise on the speed.

更新:

其实拿到1000个唯一名称后，排序也是我的一个逻辑.
如果这可以在进行排序时完成，我可以避免在排序后重复列表以找到字母表的索引.

Actually after getting the 1000 unique names, the sorting is also done by one of my logics.
If this can be done while doing the sorting itself, I can avoid the reiteration on the list after sorting to find the indices for the alphabets.

这可能吗?

谢谢，
森

推荐答案

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

So I came up with my own solution for this.

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()

}

欢迎所有评论.

这篇关于查找以给定字母开头的第一个单词的索引形成按字母顺序排序的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！