41.1 數(shù)據(jù)流中的中位數(shù)
后面再看
考慮將數(shù)據(jù)序列從中間開(kāi)始分為兩個(gè)部分，左邊部分使用大根堆表示，右邊部分使用小根堆存儲(chǔ)刻盐。每遍歷一個(gè)數(shù)據(jù)，計(jì)數(shù)器count增加1乌昔，當(dāng)count是偶數(shù)時(shí)隙疚，將數(shù)據(jù)插入小根堆；當(dāng)count是奇數(shù)時(shí)磕道，將數(shù)據(jù)插入大根堆。當(dāng)所有數(shù)據(jù)遍歷插入完成后（時(shí)間復(fù)雜度為O(logn)O(logn)行冰，如果count最后為偶數(shù)溺蕉，則中位數(shù)為大根堆堆頂元素和小根堆堆頂元素和的一半伶丐；如果count最后為奇數(shù)，則中位數(shù)為小根堆堆頂元素疯特。
下午重來(lái)
public class Solution {
// 大頂堆哗魂，存儲(chǔ)左半邊元素
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
// 小頂堆，存儲(chǔ)右半邊元素漓雅，并且右半邊元素都大于左半邊
private PriorityQueue<Integer> right = new PriorityQueue<>();
// 當(dāng)前數(shù)據(jù)流讀入的元素個(gè)數(shù)
private int N = 0;
public void Insert(Integer val) {
// 插入要保證兩個(gè)堆存于平衡狀態(tài)
if (N % 2 == 0) {
// N 為偶數(shù)的情況下插入到右半邊录别。
// 因?yàn)橛野脒呍囟家笥谧蟀脒叄切虏迦氲脑夭灰欢ū茸蟀脒呍貋?lái)的大邻吞，
// 因此需要先將元素插入左半邊组题，然后利用左半邊為大頂堆的特點(diǎn)，取出堆頂元素即為最大元素抱冷，此時(shí)插入右半邊
left.add(val);
right.add(left.poll());
} else {
right.add(val);
left.add(right.poll());
}
N++;
}
public Double GetMedian() {
if (N % 2 == 0)
return (left.peek() + right.peek()) / 2.0;
else
return (double) right.peek();
}
}
41.2 字符流中第一個(gè)不重復(fù)的字符
因?yàn)橐粋€(gè)字符不會(huì)超過(guò)8位崔列，所以創(chuàng)建一個(gè)大小為256的整形數(shù)組，創(chuàng)建一個(gè)List旺遮，存放只出現(xiàn)一次的字符赵讯。insert時(shí)先對(duì)該字符所在數(shù)組位置數(shù)量+1，再判斷該位置的值是否為1耿眉，如果為1边翼，就添加到List中，不為1鸣剪，則表示該字符已出現(xiàn)不止1次讯私，然后從List中移除，取出時(shí)先判斷List的size是否為0西傀，不為0直接List.get(0)斤寇，就可以得到結(jié)果，否則返回‘#’
方法不難想拥褂，主要是實(shí)現(xiàn)由坑娘锁，看注釋
//41.2 字符流中第一個(gè)不重復(fù)的字符
private static int[] chacnt = new int[256];
private static ArrayList<Character> lst = new ArrayList<Character>();
public static void insert(char ch){
chacnt[ch]++;
if(chacnt[ch]==1){
lst.add(ch);
}else{
//注意這裡要強(qiáng)制轉(zhuǎn)換一下
lst.remove((Character)ch);
}
}
public static char findFist() {
if (lst.size() == 0) {
return '#';
} else {
return lst.get(0);
}
}
- 連續(xù)子數(shù)組的最大和
判斷和是否大于0，大于0繼續(xù)加饺鹃，小于0重新開(kāi)始
//42. 連續(xù)子數(shù)組的最大和
public static int maxsum(int[] arr) {
if (arr == null || arr.length == 0)
return -1;
int sum=0;
int res=0;
for(int val:arr){
if(sum>0) {
sum= val+sum;;
} else{
sum=val;
}
res=Math.max(sum, res);
}
return res;
}
- 從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)
很繞
不直觀的算法 參考 https://blog.csdn.net/yi_afly/article/details/52012593 沒(méi)太理解莫秆，今天再想想
若weight為0，則1出現(xiàn)次數(shù)為roundbase
若weight為1悔详，則1出現(xiàn)次數(shù)為roundbase+former+1
若weight大于1镊屎，則1出現(xiàn)次數(shù)為rount*base+base
public static int count(int n) {
if(n<1) return 0;
int round = n;
int base =1;
int cnt=0;
while(round>0) {
int weight = round%10;
round/=10;
cnt+= cnt*base;
if(weight==1)
cnt+=(n%base)+1;
else if(weight>1)
cnt+=base;
base*=10;
}
return cnt;
}
