1.1.29

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

查找小于指定值的元素数量可以多次使用二分查找实现。

例如:
序号:0 1 2 3 4 5 6 7 8
元素:1 2 2 2 2 2 2 2 3
二分查找返回 4
再次在 0~3 之间查找
二分查找返回 1
再次在 0~1 之间查找
二分查找返回 -1,没有指定值了
因此小于该值的元素数量就是 1 – 0 = 1 个

用同样的方法可以找到大于指定值的元素个数,
从总数中减去这两个数值就是等于指定值的元素数量。

代码

static void Main(string[] args)
        {
            int[] WhiteList = new int[] { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6 };

            Array.Sort<int>(WhiteList);

            Console.WriteLine("Type the numbers you want to query: ");
            string input = Console.ReadLine();
            int[] Query = new int[input.Split(' ').Length];
            for (int i = 0; i < Query.Length; ++i)
            {
                Query[i] = int.Parse(input.Split(' ')[i]);
            }

            Console.WriteLine("Result:");
            foreach (int n in Query)
            {
                int less = rank(n, WhiteList);
                int equal = count(n, WhiteList);
                Console.WriteLine($"Less: {less} Equal: {equal}");
            }
        }

        //返回数组中相等元素的个数
        public static int count(int key, int[] a)
        {
            int lowerBound = rank(key, a);
            int upperBound = lowerBound;

            if (lowerBound == -1)
                return 0;

            int result = 0;
            while (true)
            {
                result = rank(key, a, upperBound + 1, a.Length - 1);
                if (result == -1)
                    break;
                if (result > upperBound)
                {
                    upperBound = result;
                }
            }

            return upperBound - lowerBound + 1;
        }

        //返回数组中小于该数的数字个数
        public static int rank(int key, int[] a)
        {
            int mid = rank(key, a, 0, a.Length - 1);
            if (mid == -1)
                return 0;
            int result = mid;
            while (true)
            {
                result = rank(key, a, 0, mid - 1);

                if (result == -1)
                    break;
                if (result < mid)
                    mid = result;
            }
            return mid;
        }

        //二分查找
        public static int rank(int key, int[] a, int lo, int hi)
        {

            if (lo > hi)
            {
                return -1;
            }

            int mid = lo + (hi - lo) / 2;

            if (key < a[mid])
            {
                return rank(key, a, lo, mid - 1);
            }
            else if (key > a[mid])
            {
                return rank(key, a, mid + 1, hi);
            }
            else
            {
                return mid;
            }
        }
    }
上一题 下一题