我需要做的事情是这样：在JAVA中将一堆数一个个插入一个数组或集合中，需要在尽量少的时间内找到新插入的数在原有的数组中的排名

Question

比如我插入了2,3,5,19
待插入的是6，那么它在这一堆数字中的排名就是2
我上网搜索过用sortedmap等数据结构，但是不支持插入重复的数值....
有没有什么类似的算法或者数据结构可以实现这一要求....

Answer 1

使用数组的方式进行编写了

public class IndexNumberPosition {
    //存放数据
    private static int[] array = new int[100];
    //表示操作的次数,也表示数组中存在的数据总数
    private static int size = 0;

    /**
     * 添加数据到数组中,返回添加之后的下标
     *
     * @param number 数据
     * @return 添加之后的下标
     */
    public static int add(int number) {
        //查找元素所在的位置,小于或等于元素的位置
        int index = search(number);
        size++;
        //如果数组为空
        if (index == -1) return 0;
        //数组不为空
        moveArray(index, number);
        return index;
    }

    /**
     * 将数组中的位置集体往后移动一位,然后把元素赋值给空出来的位置
     *
     * @param index  查找元素所在的下标
     * @param number 元素值
     */
    private static void moveArray(int index, int number) {
        //将index的后面的数据全部往后移动一位
        if (size - index >= 0) System.arraycopy(array, index, array, index + 1, size - index);
        array[index] = number;
    }

    /**
     * 查找元素小于或等于给定值所在的位置
     * 比如:1,3,4,5,6 查找元素2,返回1
     *
     * @param number 待查询的元素
     * @return 小于或等于元素下标的位置
     */
    public static int search(int number) {
        //如果元素大于数组中的最大值
        if (size != 0 && array[size - 1] < number) return size;
        //其他情况
        for (int i = 0; i < size; i++) {
            if (number <= array[i]) {
                return i;
            }
        }
        //如果数组为空
        array[0] = number;
        return -1;
    }

}