- Q1: Find the smallest way from array:
- function findMin(arr) {
- let min = arr[0];
- for (let i = 1; i <arr.length; i++) {
- if (arr[i] < min) {
- min = arr[i];
- }
- }
- return min; // 1
- }
- O(n), cannot be improved anymore, because we have to loop though the array once.
- Q2: Find 2nd smallest value, naive solution:
- function findSndMin(arr) {
- let min = arr[0];
- let min2 = arr[1];
- for (let i = 0; i < arr.length; i++) {
- if (arr[i] < min) {
- min2 = min;
- min = arr[i];
- } else if (arr[i] !== min && arr[i] < min2) {
- min2 = arr[i];
- }
- }
- return min2; // 2
- }
- Q3: Find nth smallest value:
1. Sorting cannot be the best solution, because it do more works, we only care Nth, means I don't care 0...n-1 is sorted or not or n +1....arr.length is sorted or not.
- 2. Patition: avg can achieve n + n/2 + n/4 + n/8 .... = 2n ~~ O(n), worse: O(n^2)
- function findNthMin(arr, m) {
- const pivot = arr[0];
- let smaller = [];
- let larger = [];
- for (let i = 1; i < arr.length; i++) {
- if (arr[i] < pivot) {
- smaller.push(arr[i]);
- } else {
- larger.push(arr[i]);
- }
- }
- smaller.push(pivot);
- arr = [...smaller, pivot, ...larger];
- if (m> smaller.length) {
- return findNthMin(larger, m - smaller.length);
- } else if (m < smaller.length) {
- return findNthMin(smaller, m);
- } else {
- return arr[m - 1];
- }
- }
- const data = [3, 1, 5, 7, 2, 8];
- const res = findNthMin(data, 4);
- console.log(res);
- [Algorithm] Find Nth smallest value from Array
来源: http://www.bubuko.com/infodetail-2945833.html