i want to Find the smallest difference in array(not sorted) c just nlogn Temporal complexity;
just nlong Temporal complexity. i think we need to use merge sort algoritm or change it.
sample : In=> [10, 30, 89, 120, 88, 3000, 5]
Out => 1
CodePudding user response:
Definitely, you can sort both arrays O(nlogn) and compare them O(n) to find your item. Nevertheless, you can also use QuickSelect algorithm O(n) for finding the [n/2]th item in your array. Then your array will be divided into two parts which the items in the first half are less than the items in the second half. Now compare the summation of the first halves and the second halves in both arrays, and continue the algorithm recursively on the halves which are not equal. It will be O(nlogn) on the average case.
CodePudding user response:
First, sort the array using mergesort (O(nlogn) complexity). Then run minimum difference between every adjacent couple of cells using a loop