从数组中找出第n大的数

2021/8/24 23:11:27

本文主要是介绍从数组中找出第n大的数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

基本思路就是随便找一个数,遍历数组,比这个数大的那么放到这个数的左边,比这个数小的放在这个数的右边。如果左边的数+1 == 这个n   那么当前这个数就是我们需要返回的,否则遍历左侧或者右侧的数组,条件是 如果左边的数很少,比如只有1个 ,你需要得到第3大的数,明显需要遍历右侧,否则就遍历左侧 。如此递归进行

 public static    class Util

{

          public static  int INVALID_INT_VALUE = 1 << 31;
        //nStartIndex为数组开始的索引 nArrayLength为数组的长度 k为第k大的数 
        public static int FindMaxValueN(int[] array,int nStartIndex, int nArrayLength, int k) 
        {
            if(nStartIndex < 0 || nArrayLength > array.Length || k > array.Length)
            {
                return INVALID_INT_VALUE;
            }
            int refValue = array[nStartIndex];
            int nLeftCount = 0;
            for(int i = nStartIndex; i < nStartIndex + nArrayLength; i++)
            {
                if(refValue < array[i] )
                {
                    int recordValue = array[i];
                    for(int j = i-1; j >= 0; j--)
                    {
                        array[j + 1] = array[j];
                    }
                    array[nStartIndex] = recordValue;
                    ++nLeftCount;
                }
            }
           
            if (nLeftCount == k - 1)
            {
                return array[nStartIndex + k-1];
            }
            else if (nLeftCount > k - 1)
            {
                //遍历左测 
                return FindMaxValueN(array, nStartIndex, nLeftCount, k );
            }
            else
            {
                //遍历右测 
                return FindMaxValueN(array, nStartIndex + nLeftCount + 1, nArrayLength - nLeftCount -1,k - nLeftCount - 1 );
            }
        }

}

//测试用例 

static void Main2(string[] args)
        {
            Console.WriteLine((5 << 2) & 6);
            int[] a = { 1, 2, 3, 4, 5 };
            int[] b = { 5, 4, 3, 2, 1 };
            int[] c = { 1, 5, 3, 4, 2 };
            int[] d = { 2, 3, 1, 4, 5 };
            for(int i = 0; i < 5; i++)
            {
                Console.WriteLine("-------第" + (i+1) + "大的数为");
                Console.WriteLine( Util.FindMaxValueN(a, 0, a.Length, i+1));
                Console.WriteLine(Util.FindMaxValueN(b, 0, b.Length, i+1));
                Console.WriteLine(Util.FindMaxValueN(c, 0, c.Length, i+1));
                Console.WriteLine(Util.FindMaxValueN(d, 0, d.Length, i+1));
                Console.WriteLine("-------end");
            }
            Console.ReadKey();
        }



这篇关于从数组中找出第n大的数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程