java 实现从无序数组中 找出第k大的数, 无序数组充许有重复元素

时间:2022-05-16 10:54:42

要求找出第几名的元素是什么(找出B[i]的值)? 找出第k名的元素的值。

         先从A中随机一个下标index1, 然后进行一趟快速排序等到新数组A1,排完了就知道index1对应的元素在A1中的新下标index2. 如果k等于index2,则A1[index2]就是要找的值。

如果 k小于index2 ,则在A1的以index2为分界的左部分去找。

如果 k大于index2 ,则在A1的以index2为分界的右部分去找。


===========测试用的代码=================

package test;
import org.junit.Test;
public class RankKthTest
{
    @Test
    public void test1()
    {
        RankKth rk = new RankKth();

        // 0,1,2,3,4,5,6,07,08,09,10,011,012
        // 0,1,2,2,3,3,5,35,61,75,75,324,513
        int[] arr = { 3, 2, 35, 1, 2, 3, 5, 61, 324, 513, 75, 0, 75 };
        int value;
        value = rk.searchKthEle(arr, 12);// ?找出最大数
        System.out.println(value);

        value = rk.searchKthEle(arr, 0);// ?找出最小数
        System.out.println(value);

        value = rk.searchKthEle(arr, 6);// ?找出第6名的数
        System.out.println(value);

    }
}
测试结果:

找出最大数

head=0, rear=12, index=6
3,2,35,1,2,3,5,61,324,513,75,0,75,
index=6, value=5
3,2,0,1,2,3,5,61,324,513,75,35,75,
=========
head=7, rear=12, index=9
3,2,0,1,2,3,5,61,324,513,75,35,75,
index=12, value=513
3,2,0,1,2,3,5,61,324,75,75,35,513,
=========
513
$$$$$$$$$$$$$$$$$$

找出最小数
head=0, rear=12, index=6
3,2,0,1,2,3,5,61,324,75,75,35,513,
index=6, value=5
3,2,0,1,2,3,5,61,324,75,75,35,513,
=========
head=0, rear=5, index=2
3,2,0,1,2,3,5,61,324,75,75,35,513,
index=0, value=0
0,2,3,1,2,3,5,61,324,75,75,35,513,
=========
0
$$$$$$$$$$$$$$$$$$

找出第6大的数
head=0, rear=12, index=6
0,2,3,1,2,3,5,61,324,75,75,35,513,
index=6, value=5
0,2,3,1,2,3,5,61,324,75,75,35,513,
=========
5

 

 

===========================================================

package test;
public class RankKth
{

    /**
     * invokes this method to allow array containing duplicate elements
     *
     * @param index
     * @param direction
     * @return
     */
    private int moveBound(int index, String direction)
    {
        if (direction.equals("left"))
        {
            while (true)
            {
                if (index - 1 >= 0)
                {
                    if (intArr[index] == intArr[index - 1])
                        index--;
                    else break;
                }
                else break;
            }
        }
        else
        {
            while (true)
            {
                if (index + 1 < intArr.length)
                {
                    if (intArr[index] == intArr[index + 1])
                        index++;
                    else break;
                }
                else break;
            }
        }
        return index;
    }

    private int[] intArr;

    /**
     * get the k'th element's value
     *
     * @param intArr
     * @return value of k'th element
     */
    public int searchKthEle(int[] intArr, int k)
    {
        if (k < 0 || k > intArr.length - 1) return Integer.MAX_VALUE;
        this.intArr = intArr;
        int retIndex, head, rear;
        head = 0;
        rear = intArr.length - 1;
        retIndex = swapAccrodingToIndex(head, rear);
        for (;;)
        {
            if (retIndex == k || head >= rear)
                return intArr[retIndex];
            else if (retIndex < k)
            {
                head = retIndex + 1;
                head = moveBound(head, "right");
                retIndex = swapAccrodingToIndex(head, rear);
            }
            else
            {
                rear = retIndex - 1;
                rear = moveBound(rear, "left");
                retIndex = swapAccrodingToIndex(head, rear);
            }
        }
    }

    /**
     * find out element's index in a array when the array is sorted.
     *
     * @param intArr
     *            a array sorted or not sorted
     * @param element
     *            a element in the array.
     * @return index
     */
    private int swapAccrodingToIndex(int head, int rear)
    {
        int index = (rear - head) / 2 + head;
        System.out.println(String.format("head=%d, rear=%d, index=%d", head,
                rear, index));
        disp();

        /*
         * head=0, rear=1, index=0 1,2,2,35,3,3,5,61,324,513, index=1, value=2
         * 1,2,2,35,3,3,5,61,324,513,
         */
        int splitEle = intArr[index];
        int i, j;
        i = head;
        j = rear;
        while (i < j)
        {
            while (i < index)
            {
                if (intArr[i] > splitEle)
                {
                    intArr[index] = intArr[i];
                    index = i;
                    break;
                }
                i++;
            }
            while (j > index)
            {
                if (intArr[j] < splitEle)
                {
                    intArr[index] = intArr[j];
                    index = j;
                    break;
                }
                j--;
            }
        }
        intArr[index] = splitEle;

        System.out.println(String.format("index=%d, value=%d", index,
                intArr[index]));
        disp();
        System.out.println("=========");
        return index;// element's index in a sorted arr
    }

    private void disp()
    {
        for (int i = 0; i < intArr.length; i++)
        {
            System.out.print(intArr[i] + ",");
        }
        System.out.println();
    }
}