The maximum sum of the median and continuous subarrays in the data stream of JS algorithm

This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021

The median in the data stream

41. Median in data stream

Difficulty: difficulty

Topic: leetcode-cn.com/problems/sh…

How do I get a median in a data stream? If an odd number of values are read from the data stream, the median is the number in the middle of all values sorted. If an even number of values are read from the data stream, the median is the average of the middle two numbers sorted by all the values.

For example,

The median for [2,3,4] is 333

The median of [2,3] is (2+3)/2=2.5(2+3)/2 =2.5(2+3)/2 =2.5

Design a data structure that supports the following two operations:

Void addNum(int num) – Adds an integer from the data stream to the data structure
Double findMedian() – Returns the current median for all elements.

Example 1:

Input: [" MedianFinder ", "addNum", addNum ""," findMedian ", "addNum", "findMedian"] [[], [1], [2], [], [3], []] output: [null, null, null, 1.50000, null, 2.00000]Copy the code

Example 2:

Input: [" MedianFinder ", "addNum", "findMedian", "addNum", "findMedian"] [[], [2], [], [3], []] output: [null, null, 2.00000, null, 2.50000]Copy the code

Limit: Up to 50000 calls to addNum and findMedian

Answer key

Method one direct method

Sort all elements first, calculate the median, and then extract the median.

/** * initialize your data structure here. */
var MedianFinder = function () {
  this.result = [];
};

/ * * *@param {number} num
 * @return {void}* /
MedianFinder.prototype.addNum = function (num) {
  this.result.push(num);
};

/ * * *@return {number}* /
MedianFinder.prototype.findMedian = function () {
  const len = this.result.length;
  if(! len)return null;
  this.result.sort((a, b) = > a - b);
  const mid = Math.floor((len - 1) / 2); // round down
  if (len % 2) {
    return this.result[mid];
  }
  return (this.result[mid] + this.result[mid + 1) /2;
};

/** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */
Copy the code

Time complexity: O(NlogNNlogNNlogN), sort uses quicksort
Space complexity: O(NlogNNlogNNlogN)

Method 2 binary search

Keep the array in order before each element is added, and use binary lookup to find the correct location and insert its new element.

var MedianFinder = function () {
  this.result = [];
};

MedianFinder.prototype.addNum = function (num) {
  const len = this.result.length;
  if(! len) {this.result.push(num);
    return;
  }

  let l = 0,
    r = len - 1;
  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    if (this.result[mid] === num) {
      this.result.splice(mid, 0, num);
      return;
    } else if (this.result[mid] > num) {
      r = mid - 1;
    } else {
      l = mid + 1; }}this.result.splice(l, 0, num);
};

MedianFinder.prototype.findMedian = function () {
  const len = this.result.length;
  if(! len)return null;
  const mid = Math.floor((len - 1) / 2);
  if (len % 2) {
    return this.result[mid];
  }
  return (this.result[mid] + this.result[mid + 1) /2;
};
Copy the code

Time complexity: O(NNN), binary search requires O(logNlogNlogN), move requires O(NNN), so O(NNN)
Space complexity: O(NNN)

Method 3 Priority queue (heap)

With the size heap, the maximum heap holds the smaller half of the data stream, and the minimum heap holds the larger one of the data stream, keeping the two heaps equal in size or the maximum heap = the minimum heap + 1. (Odd and even)

When findMedian is called, the median is either the top element of the largest heap or (top of the largest heap + top of the smallest heap) / 2. (Odd and even)

The practice of maintaining equality:

Num is placed in the maximum heap, the top element of the maxHeap, and the minimum heap minHeap.
If the size of the maximum heap is less than the size of the minimum heap, take the top element of the minHeap and place it in the maxHeap.

JavaScript does not have a heap function, you need to write their own, the following is the binary heap implementation code:

const defaultCmp = (x, y) = > x > y;// It is used to control the judgment, so as to realize the maximum heap and the minimum heap switch
const swap = (arr, i, j) = > ([arr[i], arr[j]] = [arr[j], arr[i]]);// It is used to swap two nodes
class Heap {
	constructor(cmp = defaultCmp){
    this.container = []; // It is used to store data
    this.cmp = cmp;
  }
  
  push_heap(data) { // Used to add a node
    const { container, cmp } = this;
    container.push(data); // First insert the value into the last bit of the binary heap
    let index = container.length - 1;// Data coordinates
    while(index){
      let parent = Math.floor((index - 1) / 2); // The parent node of data
      if(! cmp(container[index], container[parent])){For example, if the child node is smaller than the parent node, return the maximum heap.
        return;
      }
      swap(container, index, parent);// If the child is larger than the parent, switch
      index = parent;// Continue the recursive comparison}}pop_heap() { // It is used to eject the node. After eject the heap top element, the heap needs to be adjusted and the heap top value is returned.
    const { container, cmp } = this;
    if(! container.length){return null;
    }
    swap(container, 0, container.length - 1);// Swap the top element with the tail element
    const res = container.pop();// Pop the tail element
    const length = container.length;
    let index = 0, exchange = index * 2 + 1;// Exchange is the left node subscript
    
    while(exchange < length) {
      let right = index * 2 + 2;
      // In the maximum heap case, if there is a right node, and the value of the right node is greater than the value of the left node
      if(right < length && cmp(container[right], container[exchange])) {
        exchange = right;
      }
      if(! cmp(container[exchange], container[index])) {break;
      }
      swap(container, exchange, index);
      index = exchange;
      exchange = index * 2 + 1;
    }
    return res;
  }
  
  top() { // Output the top value of the heap
    if(this.container.length) return this.container[0];
    return null; }}Copy the code

Now that we have the heap implementation, let’s look at the problem:

var MedianFinder = function() {
	this.maxHeap = new Heap();
  this.minHeap = new Heap((x, y) = > x < y);
};

MedianFinder.prototype.addNum = function(num) {
	this.maxHeap.push_heap(num);
  this.minHeap.push_heap(this.maxHeap.pop_heap());
  
  if(this.maxHeap.container.length < this.minHeap.container.length){
    this.maxHeap.push_heap(this.minHeap.pop_heap()); }}; MedianFinder.prototype.findMedian =function() {
	return this.maxHeap.container.length > this.minHeap.container.length ? this.maxHeap.top() : (this.maxHeap.top() + this.minHeap.top()) / 2;
};
Copy the code

Time complexity: O(logNlogNlogN)
Space complexity: O(NNN)

Maximum sum of contiguous subarrays

Sword finger Offer 42. Maximum sum of contiguous subarrays

Difficulty: Easy

Topic: leetcode-cn.com/problems/li…

Enter an integer array in which one or more consecutive integers form a subarray. Find the maximum sum of all subarrays.

The required time complexity is O(NNN)

Example 1:

Input: nums = [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.Copy the code

Tip:

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

Answer key

Method 1 dynamic programming DP

Create an array dp[I] that “records the maximum sum of contiguous subarrays with subscripts [0, I] in numS”.

Ideas:

The initial valuedp[0] = nums[0]
ifdp[i - 1] > 0,dp[i] = nums[i] + dp[i - 1]
ifdp[i - 1] <= 0,dp[i] = nums[i]

/ * * *@param {number[]} nums
 * @return {number}* /
var maxSubArray = function (nums) {
  const dp = [];
  dp[0] = nums[0]
  let max = dp[0];
  for (let i = 1; i < nums.length; i++) {
    dp[i] = nums[i];
    if (dp[i - 1] > 0) {
      dp[i] += dp[i - 1];
    }
    max = max > dp[i] ? max : dp[i];
  }
  return max;
};
Copy the code

Time complexity: O(NNN)
Space complexity: O(NNN)

Method two dynamic programming space optimization

Method 1 opens up an array, and we can further optimize it to operate on the original array.

var maxSubArray = function(nums) {
  let max = nums[0];
  for(let i = 1; i < nums.length; i++){
    if(nums[i - 1] > 0){
      nums[i] += nums[i - 1];
    }
    max = max > nums[i] ? max : nums[i];
  }
  return max;
}
Copy the code

Time complexity: O(NNN)
Space complexity: O(111)

Method 3 uses the reduce function

arr.reduce(callback(accumulator, currentValue[, index[, array]])[, initialValue])

The callback function takes four arguments:

accumulator: The return value of the accumulator’s cumulative callback; It is the cumulative value returned when the callback was last called, orinitialValue.
CurrentValue: The element being processed in the array.
index(Optional) : Index of the current element being processed in the array. If providedinitialValue, the start index is 0; otherwise, the index starts from 1.
Array (Optional) : Array to call reduce().
initialValue(Optional) : As the first callcallbackThe value of the first argument to the function. If no initial value is provided, the first element in the array is used. Calling reduce on an empty array with no initial value will report an error.

The return value is the cumulative processing result of the function.

// Borrow the idea of dynamic programming
var maxSubArray = function(nums) {
	let max = -Infinity;
  nums.reduce((total, cur, i) = > {
    if(total > 0){
      total += cur;
    }else{
      total = cur;
    }
    max = max > total ? max : total;
    return total;
  },0) // total starts with 0
  return max;
};
Copy the code

Law 4 The law of greed

var maxSubArray = function(nums) {
  let max = nums[0];
  let cur = nums[0];
  for(let i = 1; i < nums.length; i++){
    cur = Math.max(nums[i], cur + nums[i]);
    max = Math.max(max, cur);
  }
  return max;
}
Copy the code

Time complexity: O(NNN)
Space complexity: O(111)

Practice every day! The front end is a new one. I hope I can get a thumbs up

The maximum sum of the median and continuous subarrays in the data stream of JS algorithm

The median in the data stream

Answer key

Method one direct method

Method 2 binary search

Method 3 Priority queue (heap)

Maximum sum of contiguous subarrays

Answer key

Method 1 dynamic programming DP

Method two dynamic programming space optimization

Method 3 uses the reduce function

Law 4 The law of greed

Related Posts

Native JS Snake, detailed notes, mind maps

Vue uses axios image upload problem

(2) Develop a micro channel mini program personalized resume, can open the door of dachang and get tickets? (Attached source code)