2.3.15

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

解答

事实上只需要修改快速排序的切分方法,分两次进行切分。
首先选第一个螺母作为枢轴,找到对应的螺丝($ O(n) $)放到第一位,对螺丝数组进行切分。
然后再用找到的螺丝对螺母数组进行切分。

螺母类,实现了对螺丝类的 IComparable 接口

/// <summary>
/// 螺母类。
/// </summary>
public class Nut<T> : IComparable<Bolt<T>> where T : IComparable<T>
{
    /// <summary>
    /// 螺母的值。
    /// </summary>
    public T Value { get; set; }

    /// <summary>
    /// 螺母的构造函数。
    /// </summary>
    /// <param name="value">螺母的值。</param>
    public Nut(T value) => this.Value = value;

    /// <summary>
    /// 比较方法,螺母只能和螺丝比较。
    /// </summary>
    /// <param name="other">需要比较的螺丝。</param>
    /// <returns></returns>
    public int CompareTo(Bolt<T> other)
    {
        return this.Value.CompareTo(other.Value);
    }
}

类似的有螺丝类。

/// <summary>
/// 螺丝类。
/// </summary>
public class Bolt<T> : IComparable<Nut<T>> where T : IComparable<T>
{
    /// <summary>
    /// 螺丝的值。
    /// </summary>
    public T Value { get; set; }

    /// <summary>
    /// 螺丝的默认构造函数。
    /// </summary>
    /// <param name="value">螺丝的值。</param>
    public Bolt(T value) => this.Value = value;

    /// <summary>
    /// 比较方法,螺丝只能和螺母比较。
    /// </summary>
    /// <param name="other">需要比较的螺母。</param>
    /// <returns></returns>
    public int CompareTo(Nut<T> other)
    {
        return this.Value.CompareTo(other.Value);
    }
}

代码

修改后的排序方法。

using System;

namespace _2._3._15
{
    /// <summary>
    /// 用快排的方式解决螺母和螺帽的问题。
    /// </summary>
    public class BoltsAndNuts
    {
        private readonly Random random = new Random();

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public BoltsAndNuts() { }

        /// <summary>
        /// 对螺丝和螺母排序。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        public void Sort<T>(Bolt<T>[] bolts, Nut<T>[] nuts) where T : IComparable<T>
        {
            if (bolts.Length != nuts.Length)
                throw new ArgumentException("数组长度必须一致");

            Shuffle(bolts);
            Shuffle(nuts);
            Sort(bolts, nuts, 0, bolts.Length - 1);
        }

        /// <summary>
        /// 对螺丝和螺母排序。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        /// <param name="lo">起始下标。</param>
        /// <param name="hi">终止下标。</param>
        public void Sort<T>(Bolt<T>[] bolts, Nut<T>[] nuts, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)
                return;
            int j = Partition(bolts, nuts, lo, hi);
            Sort(bolts, nuts, lo, j - 1);
            Sort(bolts, nuts, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        /// <param name="lo">起始下标。</param>
        /// <param name="hi">终止下标。</param>
        /// <returns>切分位置。</returns>
        private int Partition<T>(Bolt<T>[] bolts, Nut<T>[] nuts, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            Bolt<T> pivotB = bolts[lo];
            // 找到对应螺丝
            for (int k = lo; k <= hi; k++)
            {
                if (nuts[k].CompareTo(pivotB) == 0)
                {
                    Exch(nuts, k, lo);
                    break;
                }
            }
            // 先用螺母去套螺丝
            while (true)
            {
                while (nuts[++i].CompareTo(pivotB) < 0)
                    if (i == hi)
                        break;
                while (pivotB.CompareTo(nuts[--j]) < 0)
                    if (j == lo)
                        break;

                if (i >= j)
                    break;
                Exch(nuts, i, j);
            }
            Exch(nuts, lo, j);

            // 再用螺丝去比较螺母
            Nut<T> pivotN = nuts[j];
            i = lo;
            j = hi + 1;
            while (true)
            {
                while (bolts[++i].CompareTo(pivotN) < 0)
                    if (i == hi)
                        break;
                while (pivotN.CompareTo(bolts[--j]) < 0)
                    if (j == lo)
                        break;

                if (i >= j)
                    break;

                Exch(bolts, i, j);
            }
            Exch(bolts, lo, j);

            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + this.random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }

        /// <summary>
        /// 交换两个元素。
        /// </summary>
        /// <typeparam name="T">元素类型。</typeparam>
        /// <param name="a">需要交换的第一个元素。</param>
        /// <param name="b">需要交换的第二个元素。</param>
        private void Exch<T>(T[] a, int lo, int hi)
        {
            T t = a[lo];
            a[lo] = a[hi];
            a[hi] = t;
        }
    }
}

另请参阅

下面这个网站给出了这道题的解法,还给出了另一种确定性算法(非随机的算法)的论文链接。
Matching Nuts and Bolts - Solution

上一题 下一题