2020年跳槽最好不要去的公司 Baozi Leetcode solution 229: Major Element II

包子面试培训

发布于 2020-02-14 16:47:00

4700

发布于 2020-02-14 16:47:00

文章被收录于专栏：包子铺里聊IT

包子小道消息@01/19/2019

新年新气象，很多同学们都跃跃欲试，老司机会告诉你，人生苦短，何妨一试？不过如果仅仅是为了尝试而尝试，那么无论尝试了多少最终都只不过是量的积累而没有质的飞跃。要钱还是要career，有时候也许不能兼得。不过如果决定跳了，根据各种没有证据来源的小道消息，如下公司大家要慎重，如果你是内部人员有着不可告人的发财详情，欢迎私信包子君，包子君给你们提供优质candidate?

那么来了，2020 毫无根据最好不要跳之公司榜单??‍♂️??‍♂️??‍♂️

Bitmain
Brandless
Zume Pizza
Getaround
Earnin
Lime
Magic Leap
Starsky Robotics
Tongdun Technology
Wework
AT&T
Mozilla

Leetcode solution 229: Major Element II

Blogger:https://blog.baozitraining.org/2020/01/leetcode-solution-229-major-element-ii.html

Youtube: https://youtu.be/86xbBTNyI_A

博客园: https://www.cnblogs.com/baozitraining/p/12059554.html

B站: https://www.bilibili.com/video/av79713468/

Problem Statement

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Problem link

Video Tutorial

You can find the detailed video tutorial here

Youtube
B站

Thought Process

It's a follow up question on Majority Element, given the hint, there should only be at most 2 elements that can satisfy the requirement (You cannot have 3 elements that all appear more than n/3 times). We can perform the voting algorithm on two potential candidates and later do an actual sum to eliminate the false positive (e.g., [1, 2, 1] would have both 1 and 2 as potential candidate, but 2 should not be included)

You can refer to Majority Element for a detailed explanation on the voting algorithm.

An extension could be changing n/3 to n/k. We just need extra arrays to store votes and candidates. It will take O(Nk) time complexity

Solutions

 1 public List<Integer> majorityElement(int[] nums) {
 2     List<Integer> res = new ArrayList<>();
 3 
 4     if (nums == null || nums.length == 0) {
 5         return res;
 6     }
 7 
 8     int candidate1 = 1;
 9     int candidate2 = 1;
10     int vote1 = 0;
11     int vote2 = 0;
12 
13     for (int i = 0; i < nums.length; i++) {
14         if (nums[i] == candidate1) {
15             vote1++;
16         } else if (nums[i] == candidate2) {
17             vote2++;
18         } else if (vote1 == 0) {  // the order of this if/else actually matters, you cannot put the 0 check first since [8, 8, 7, 7, 7]
19             candidate1 = nums[i];
20             vote1++;
21         } else if (vote2 == 0) {
22             candidate2 = nums[i];
23             vote2++;
24         } else {
25             vote1--;
26             vote2--;
27         }
28     }
29 
30     /* This is what you should do if we want to put vote1 == 0 check at the beginning
31     for (int i = 0; i < nums.length; i++) {
32         if (vote1 == 0 && candidate2 != nums[i]) {
33             candidate1 = nums[i];
34         } else if (vote2 == 0 && candidate1 != nums[i]) {
35             candidate2 = nums[i];
36         }
37         if (nums[i] == candidate1) {
38             vote1++;
39         } else if (nums[i] == candidate2) {
40             vote2++;
41         } else {
42             vote1--;
43             vote2--;
44         }
45     }
46     */
47 
48     int count1 = 0;
49     int count2 = 0;
50 
51     // need another pass to filter between the 2 candidates, e.g., [3, 2, 3], 2 is candidate but not more than 1/3
52     for (int num : nums) {
53         if (num == candidate1) {
54             count1++;
55         } else if (num == candidate2) {
56             count2++;
57         }
58     }
59 
60     if (count1 > nums.length / 3) {
61         res.add(candidate1);
62     }
63     if (count2 > nums.length / 3) {
64         res.add(candidate2);
65     }
66 
67     return res;
68 }