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

剑指 Offer 41. 数据流中的中位数
这道题是求数据流的中位数，一般情况我们可以采用排序的方式很轻松的找出中位数。如果我们采用插入排序的话，每次插入数字的时间复杂度大概是O(N)，怎么能让这个时间更短呢？那么我们可以利用大小根堆的特点把单次查找的时间复杂度缩短到O(logN)。可以使用堆，具体做法如下：
我们把数据分为两部分，一部分是小于中位数的大根堆，另一部分是大于等于中位数的小根堆。我们控制两个堆的元素个数之差<=1，这样的话，如果两堆元素个数相同，就各取堆顶元素均分得到中位数，差1就取较多元素的堆顶。
具体如何插入，我们分类讨论：

class MedianFinder {private PriorityQueue smallHeap;private PriorityQueue bigHeap;/** initialize your data structure here. */public MedianFinder() {smallHeap=new PriorityQueue();//初始默认小根堆bigHeap=new PriorityQueue(new Comparator() {//转为大根堆@Overridepublic int compare(Object o1, Object o2) {return (Integer)o2-(Integer)o1;}});}public void addNum(int num) {//保证size差值<=1if(smallHeap.size()>bigHeap.size()){//优先考虑往big插入if(num>smallHeap.peek()){//如果大于small的最小值，从small拿一个到big，num插入smallint tmp=smallHeap.poll();bigHeap.add(tmp);smallHeap.add(num);}else{bigHeap.add(num);}}else if(smallHeap.size()//优先考虑往small插入if(num<=bigHeap.peek()){//如果小于等于小根堆的最小值，从big拿一个到small，num插入bigint tmp=bigHeap.poll();smallHeap.add(tmp);bigHeap.add(num);}else{smallHeap.add(num);}}else{if(bigHeap.size()!=0&&smallHeap.size()!=0&&num>bigHeap.peek()){smallHeap.add(num);}else{bigHeap.add(num);}}}public double findMedian() {// if(smallHeap.size()!=0){//     System.out.println("a:"+smallHeap.peek());// }// if(bigHeap.size()!=0){//     System.out.println("b:"+bigHeap.peek());// }if(smallHeap.size()>bigHeap.size()){return 1.0*smallHeap.peek();}else if(smallHeap.size()return 1.0*bigHeap.peek();}else{return 1.0*(smallHeap.peek()+bigHeap.peek())/2;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

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

剑指 Offer 43. 1～n 整数中 1 出现的次数
我首先的想法是正常循环，挨个数字判断，但是很明显没有这么简单：时间超限了

既然不能循环，我觉得应该是有什么规律可循。练习了两个半小时的斯某人，决定打开题解借鉴。
以下转自：leetcode题解

得到了规律：
根据当前位 cur值的不同，分为以下三种情况：
当cur=0 时： 此位 1的出现次数只由高位 high决定，计算公式为：
high×digit
当cur=1 时： 此位 1的出现次数由高位 high和低位决定，计算公式为：
high×digit+low-1
当cur=其他数字时： 此位 1的出现次数只由高位 high决定，计算公式为：
（high+1）×digit

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;}
}

剑指 Offer 44. 数字序列中某一位的数字

剑指 Offer 44. 数字序列中某一位的数字

因为right很容易越界，我们使用long类型

class Solution {public int findNthDigit(int n) {//先把范围缩小到0-9 或者10-99 或者100-999等等long k=1;long level=1;//1代表0-9  每+1，代表范围扩大 例如2代表10-99long chars=0;//目前已占用的字符数long right=10;//每个范围所占字符数while(n>right){level++;//范围增大chars=(int)right;right=right+(level*90*k);k*=10;}n-=chars;//保存除数的结果long div=n/level;//保存取模的结果long mod=n%level;//将除数加上所在范围的基数u，比如443 得到84要+100if(k!=1)div+=k;return Long.toString(div).charAt((int)mod)-'0';}
}

共勉