c# - 从长度为 M 的未排序数组中搜索前 N 个已排序整数？

Question

关于如何从大小为 M 天前的未排序整数数组中搜索前 N 个最小/最大有序整数的算法问题面试失败。

在我看来，所有搜索问题都可以转换为具有 log2N 时间复杂度的二叉搜索树数据结构或其扩展(例如 B+ 树)来解决。

对于这道题，我先建了一颗二叉搜索树，然后搜索N个count。因此，复杂度应该是

• 构建树消耗:M * Log2 M +
• 在搜索树时消耗:N * Log2 M
• 总计:= (M + N) log2 M

我找不到更好的解决方案，所以我把我的代码贴在这里，真诚地希望你们有更好的解决方案。该代码非常随意但有效。这只是为了指出我的想法。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SearchFirstNFromM
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] m = new int[10000];   //INPUT M - int array
            int n = 10;                 //INPUT N - int

            Console.WriteLine("Integer Array");
            Random rd = new Random();
            for (int i = 0; i < m.Length; i++)
            {
                m[i] = rd.Next(0, m.Length);
                Console.Write(m[i] + " ");
            }

            Console.WriteLine();
            Console.WriteLine();
            Node root = BuildBinarySearchTree(m); //Building binary search tree
            Console.WriteLine("First N in ordered tree");
            Console.Write("Expected Result : ");
            m.OrderBy(t => t).Take(N_Counter).ToList().ForEach(t => Console.Write(t + " "));
            Console.WriteLine();
            Console.Write("Actual Result : ");
            DisplayFirstN(root);
            Console.WriteLine();
            Console.WriteLine();
            N_Counter = n; //Counter Reset
            Console.WriteLine("Last N in ordered tree");
            Console.Write("Expected Result : ");
            m.OrderByDescending(t => t).Take(N_Counter).ToList().ForEach(t => Console.Write(t + " "));
            Console.WriteLine();
            Console.Write("Actual Result : ");
            DisplayLastN(root);
            Console.WriteLine();

            Console.ReadKey();
        }

        static int N_Counter = 10;

        static void DisplayFirstN(Node root)
        {
            if (root != null)
            {
                if (root.Left != null)
                    DisplayFirstN(root.Left);

                if (N_Counter-- > 0)
                    Console.Write(root.Data + " ");

                if (root.Right != null)
                    DisplayFirstN(root.Right);
            }
        }

        static void DisplayLastN(Node root)
        {
            if (root != null)
            {
                if (root.Right != null)
                    DisplayLastN(root.Right);

                if (N_Counter-- > 0)
                    Console.Write(root.Data + " ");

                if (root.Left != null)
                    DisplayLastN(root.Left);
            }
        }

        static void DisplayTree(Node current)
        {
            if (current != null)
            {
                if (current.Left != null)
                    DisplayTree(current.Left);

                Console.Write(current.Data + " ");

                if (current.Right != null)
                    DisplayTree(current.Right);
            }
        }

        static Node BuildBinarySearchTree(int[] m)
        {
            Node root = new Node(m[0]);
            for (int i = 1; i < m.Length; i++)
            {
                Node current = root;
                while (true)
                {
                    if (m[i] >= current.Data)
                    {
                        if (current.Right == null)
                        {
                            var newNode = new Node(m[i]);
                            newNode.Parent = current;
                            current.Right = newNode;
                            break;
                        }

                        current = current.Right;
                    }
                    else
                    {
                        if (current.Left == null)
                        {
                            var newNode = new Node(m[i]);
                            newNode.Parent = current;
                            current.Left = newNode;
                            break;
                        }

                        current = current.Left;
                    }
                }
            }
            return root;
        }

        class Node
        {
            public Node(int data)
            {
                this.Data = data;
            }

            public Node Parent { get; set; }
            public Node Left { get; set; }
            public Node Right { get; set; }
            public int Data { get; set; }
        }
    }
}

Answer 1

解决此问题的更好且相对简单的方法是使用 a heap data structure .算法将是:

对于前 N 个元素，插入到堆中 (O[log N])。对于每个剩余的 M-N 个元素，将其与堆中的最小值 (O 1) 进行比较。如果更大，则删除最小的堆值并将其插入堆中(O[log N])。最后，从堆中生成一个排序列表 (O[N log N])。

总复杂度:M log N + N log N。如果 M 比 N 大得多，则这是对 M log M 排序的胜利。