发现的第一个字的起始与给定的字母形式的按字母顺序排序的列表的索引 [英] Finding the index of the first word starting with a given alphabet form a alphabetically sorted list

问题描述

根据当前实现，我会得到它载有按字母顺序排序一些源顺序（A-Z或Z-A）约1000唯一的名称的ArrayList。

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.

所以要多precise，当我选择一个字母，例如为。 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.

这可能吗？

谢谢，结果
森

Thanks,
Sen

推荐答案

于是，我想到了我自己的这个解决方案。

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

} 

所有评论欢迎。

这篇关于发现的第一个字的起始与给定的字母形式的按字母顺序排序的列表的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！