Nuggets team number online, help you Offer rimmon! Click to see details

Majority elements (Question No. 169)

The title

Given an array of size n, find most of its elements. Most elements are elements that occur in an array more than ⌊ n/2 ⌋.

You can assume that the array is non-empty and that a given array always has a plurality of elements.

Example 1:

Input: [3,2,3] Output: 3Copy the code

Example 2:

Input: [2,2,1,1, 2,2] Output: 2Copy the code

Advanced:

Try to design an algorithm with time complexity of O(n) and space complexity of O(1) to solve this problem.

link

Leetcode-cn.com/problems/ma…

explain

There are two important points here, one is n over 2, and one is inevitable.

With these two constraints there are a lot of solutions, but the one that’s hard to understand is the offset method, which of course is also the optimal solution.

Your own answer

var majorityElement = function(nums) {
  var obj = new Map()
  var res = 0
  var max = nums.length /2
  while (nums.length > 0) {
    var item = nums[0]
    obj.set(item, obj.has(item) ? obj.get(item) + 1 : 1)
    if (obj.get(item) > max) {
      res = item
      nums.length = 0
    }
    nums.shift()
  }
  return res
};
Copy the code

This is the first time given the answer, at the time was quite happy, after all, it is done, but later found out that it is a poop.

One obvious problem with this piece is that it does not terminate the loop when the condition is satisfied, which makes no sense at all, so the second time I wrote this problem I improved it by a wave 👇 :

var majorityElement = function(nums) {
  var obj = {}
      res = 0
      len = nums.length
      max = ~~(len / 2)
  for (let i = 0; i < len; i++) {
    var num = nums[i]
    obj[num] = obj[num] ? ++obj[num] : 1
    if (obj[num] > max) {
      res = num
      break
    }
  }
  return res
};
Copy the code

Is it a lot cleaner, and when the condition is met, it terminates directly, in fact, the performance of Map is better here.

A better way (sort)

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  nums.sort()
  return nums[~~(nums.length / 2)]
};
Copy the code

There’s nothing to say about that, because when you sort an array, most of the elements must be in the middle of the array, which is easy to write, but it takes order NlogN to sort, which is not optimal.

Note the sort method, which passes no arguments, and the default sort order is built when converting elements to strings and then comparing them to a sequence of UTF-16 code unit values.

It’s not from smallest to largest, although it sometimes looks like that.

But it doesn’t matter, the order doesn’t affect the number of elements, we’re done.

Better Approach (stack)

var majorityElement = function(nums) { let stack = [] for(let n of nums){ let m = stack.length if(stack[m - 1] === n || ! m){ stack.push(n) } else { stack.pop() } } return stack[0] };Copy the code

The method takes advantage of quantity, because the number of most elements must be the largest and then cancel out with other elements.

If the last element is different from the current one, the element at the top of the stack is removed. Then the most elements with the absolute advantage will win.

Better method 3 (offset)

var majorityElement = function(nums) {
  let x = 0
  let m = 0
  for(let n of nums){
    if(m === 0) x = n
    m += x === n ? 1 : -1
  }
  return x
};
Copy the code

So this is a direct counterbalance, there’s one more variable compared to the stack, but there’s less manipulation of the stack.

Note that both the stack and cancel methods actually require traversing the entire array, but the author’s answer sometimes does not require traversing the entire array.

The best time to buy and sell stocks II (Question 122)

The title

Given an array, the ith element is the ith day price of a given stock.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as you can.

Note: You cannot participate in more than one trade at a time (you must sell your shares before buying again).

Example 1:

Input: [7,1,5,3,6,4] Output: 7 Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.Copy the code

Example 2:

Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're on multiple trades at once, you have to sell your shares before buying again.Copy the code

Example 3:

Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction has been completed, so the maximum profit is 0.Copy the code

Tip:

  • 1 <= prices.length <= 3 * 10 ^ 4
  • 0 <= prices[i] <= 10 ^ 4

link

Leetcode-cn.com/problems/be…

explain

This problem is actually very simple, don’t think too complicated, what if the last number is larger than the previous number, then determine whether the next number is larger than the previous number, etc., such logic is more complicated.

When the latter is larger than the former, the difference between the two can be directly accumulated to RES. However, we need to pay attention to the performance problem here, and the author found some small differences.

Your own answer (loop)

var maxProfit = function(prices) {
    var max = 0;
    var size = prices.length;
        for (let i = 0; i < size - 1; i++)
            if (prices[i] < prices[i + 1])
                max += prices[i + 1] - prices[i];
        return max;
};
Copy the code

The for loop was used directly, it was simple, it was effective, and this was the answer a year ago.

Your own answers (reduce)

var maxProfit = function(prices) {
  return prices.reduce((total, val, i) => prices[i] < prices[i + 1] ? total + prices[i + 1] - prices[i] : total, 0)
};
Copy the code

A simple reduce. Note that it is performance intensive to judge whether the next number is larger than the current number in order to determine whether the data should be accumulated. The following method does perform better than this method.

A better answer (Math.max)

var maxProfit = function(prices) {
  return prices.reduce((total, val, i) => total += i ? Math.max(0, prices[i] - prices[i - 1]) : total, 0)
};
Copy the code

Again, it’s a reduce. But pay attention to the internal implementation details, here through Math. Max to value, so eliminating the judge whether the next element is greater than the current element, really save a part of judgement, judgement about this part of saves about 20 milliseconds, but let execution takes jumped more than 70%, from 10% the best even by more than 90%, The devil is in the details.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ