1.2.9

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

解答

首先实现一个 Counter 类,随后使用非递归版本的 BinarySearch,每进行一次 While 循环就让 Counter 加一。

代码

Counter 类

namespace _1._2._9
{
    /// <summary>
    /// 计数器类
    /// </summary>
    class Counter
    {
        private readonly string name;
        private int count;

        /// <summary>
        /// 构造函数。
        /// </summary>
        /// <param name="id">计数器的名称。</param>
        public Counter(string id)
        {
            this.name = id;
        }

        /// <summary>
        /// 计数器加一。
        /// </summary>
        public void Increment()
        {
            count++;
        }

        /// <summary>
        /// 获取当前计数值。
        /// </summary>
        /// <returns></returns>
        public int Tally()
        {
            return count;
        }

        /// <summary>
        /// 输出形如 “1 counter” 的字符串。
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            return count + " " + name;
        }
    }
}

Main 方法

using System;
using System.IO;

namespace _1._2._9
{
    /*
     * 1.2.9
     * 
     * 修改 BinarySearch(请见 1.1.10.1 节中的二分查找代码),
     * 使用 Counter 统计在有查找中被检查的键的总数并在查找全部结束后打印该值。
     * 提示:在 main() 中创建一个 Counter 对象并将它作为参数传递给 rank()
     * 
     */
    class Program
    {
        //参考 1.1.10 节的代码
        static void Main(string[] args)
        {
            Counter count = new Counter("BinarySearch");

            //读取白名单
            string[] whiteListString = File.ReadAllLines("tinyW.txt");
            int[] whiteList = new int[whiteListString.Length];

            for (int i = 0; i < whiteListString.Length; ++i)
            {
                whiteList[i] = int.Parse(whiteListString[i]);
            }
            Array.Sort(whiteList);

            //读取查询值
            string[] inputListString = File.ReadAllLines("tinyT.txt");
            int[] inputList = new int[inputListString.Length];

            for (int i = 0; i < inputListString.Length; ++i)
            {
                inputList[i] = int.Parse(inputListString[i]);
            }

            //对每一个查询值进行二分查找
            foreach (int n in inputList)
            {
                int result = rank(n, whiteList, count);
                //将不在白名单上的数据输出
                if (result == -1)
                {
                    Console.WriteLine(n);
                }
            }
            Console.WriteLine();

            //输出查询数目
            Console.WriteLine(count.Tally());
        }

        static int rank(int key, int[] a, Counter count)
        {
            int lo = 0;
            int hi = a.Length - 1;
            while (lo <= hi)
            {
                int mid = lo + (hi - lo) / 2;
                count.Increment();
                if (key < a[mid])
                {
                    hi = mid - 1;
                }
                else if (key > a[mid])
                {
                    lo = mid + 1;
                }
                else
                {
                    return mid;
                }
            }
            return -1;
        }
    }
}
上一题 下一题