c# - Search first N sorted integers from an unsorted array length M? -

c# - Search first N sorted integers from an unsorted array length M? -

failed interview on algorithm question how search first n minimum/maximum ordered integers unsorted integer array size m days ago.

from perspective, search problems can converted solved binary search tree info construction has log2n time complexity or extension such b+ tree.

for problem, build binary search tree @ first , search n count afterwards. therefore, complexity should

consumed in building tree : m * log2 m + consumed in searching tree : n * log2 m total : = (m + n) log2 m

i can't find improve solution, post code here , sincerely hope guys have improve one. code casual works. point out idea.

using system; using system.collections.generic; using system.linq; using system.text; namespace searchfirstnfromm { class programme { 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(); (int = 0; < 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]); (int = 1; < 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; } } } homecoming 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 info { get; set; } } } }

a improve , relatively simple way solve utilize a heap info structure. algorithm be:

for first n elements, insert heap (o[log n]). each of remaining m-n elements, compare minimum value in heap (o1). if greater, delete smallest heap value , insert heap (o[log n]). lastly, generate sorted list heap (o[n log n]).

total complexity: m log n + n log n. if m much bigger n, win on m log m sort.

c# arrays algorithm data-structures binary-search-tree