Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Q: Write a function that takes a list of integers and returns the 4 highest in O(n) time.
- A: Here, I use the merge sort algorithm since it uses O(n) space complexity and O(log(n)) runtime complexity. The following is my approach:
- 1. First, divide the array into halves:
- ```javascript
- arr = [1, 5, 6, 11, 3, 4, 8, 13];
- const mergeSort = (arr) => {
- // end function when array consists of only one element
- if (arr.length === 1){
- return arr
- }
- // divide the array in half, taking into account the length of the array may be an odd number
- const middle = Math.floor(arr.length / 2);
- // create two arrays called left and right
- const left = arr.slice(0, middle);
- const right = arr.slice(middle, arr.length);
- // pass the two arrays into the merge helper function
- return merge(left, right)
- }
- ```
- 2. Then, merge the individual arrays using a helper function merge algorithm:
- ```javascript
- // O(n) algorithms have out of place complexity and need an extra array into which to sort the elements
- let result = [];
- let idxLeft = 0
- let idxRight = 0
- // iterate over the left and right arrays as long as the index is less than the length of the array
- while (idxLeft < left.length && idxRight < right.length) {
- // compare the elements in each array starting from index 0
- // if the number on the left is less than the number on the right
- if (left[idxLeft] <= right[idxRight]) {
- // push the left element into the result array
- result.push(left[idxLeft]);
- // increment the index
- idxLeft++
- } else {
- // otherwise, push the right element into the result array
- result.push(right[idxRight]);
- // increment the index (0 becomes 1, 1 becomes 2 ... )
- idxRight++
- }
- // in the result concatenate the sorted left and right arrays
- let mergedArr = result.concat(left.slice(idxLeft).concat(right.slice(idxRight)))
- // pass the newly merged array and number of items to return, into the helper function
- fourLargest(mergedArr, 4)
- }
- ```
- 3. Finally, return the 4 largest elements in the now sorted and merged array:
- ```javascript
- const fourLargest = (arr, n) => {
- // the slice method is used to return the four elements from the end of the sorted array
- let sliced = arr.slice(-n);
- console.log(sliced)
- }
- ```
- 4. Don't forget to call the mergeSort function :-)
- ```javascript
- // call the mergeSort function and pass in the array to be sorted
- mergeSort(arr)
- ```
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement