大家好，我是方圆
无它，唯手熟尔

---

剑指 Offer 39. 数组中出现次数超过一半的数字

• 思路：遇到同样的数字票数加一，不同的减一，众数的票数一定大于1

class Solution {public int majorityElement(int[] nums) {int x = 0,votes = 0;for(int num : nums){if(votes == 0) x = num;votes += x == num ? 1 : -1;}return x;}
}

剑指 Offer 40. 最小的k个数

• 思路：使用PriorityQueue

class Solution {public int[] getLeastNumbers(int[] arr, int k) {PriorityQueue<Integer> pq = new PriorityQueue<>();for(int num : arr) pq.offer(num);int[] res = new int[k];for(int i = 0;i< k;i++) res[i] = pq.poll();return res;}
}

剑指 Offer 41. 数据流中的中位数

• 思路：利用大顶堆与小顶堆，大顶堆存左边的小值，小顶堆存右边的大值

class MedianFinder {Queue<Integer> A,B;/** initialize your data structure here. */public MedianFinder() {A = new PriorityQueue<>();//小顶堆，存储后边较大的部分B = new PriorityQueue<>((x,y) -> y - x);//大顶堆，存储前边较小的部分}public void addNum(int num) {//在这里进行排序if(A.size() != B.size()){//此时A堆中数量多，加入num//再弹出最小的num给BA.add(num);B.add(A.poll());}else{//AB中值一样多的时候，num加入B中//并且要把最大的值拿出来存到A里//始终保持A堆中数量多B.add(num);A.add(B.poll());}}public double findMedian() {return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;}
}

剑指 Offer 42. 连续子数组的最大和

class Solution {public int maxSubArray(int[] nums) {int ans = nums[0];int sum = 0;//若sum对当前值有增益，则加上//否则就不要之前的sum了for(int num : nums){if(sum > 0){sum += num;}else{sum = num;}ans = Math.max(ans,sum);}return ans;}
}

剑指 Offer 43. 1~n整数中1出现的次数

class Solution {public int countDigitOne(int n) {int digit = 1, res = 0;int high = n / 10, cur = n % 10, low = 0;while(high != 0 || cur != 0) {if(cur == 0) res += high * digit;else if(cur == 1) res += high * digit + low + 1;else res += (high + 1) * digit;low += cur * digit;cur = high % 10;high /= 10;digit *= 10;}return res;}
}

---

呼！