Jie's blog

混就完事了


  • 首页

  • 关于

  • 分类

  • 归档

  • 日程表

找出数组中超过一半以及三分之一的数

发表于 2018-10-11 | 分类于 java

找出数组中超过一半的数(假设存在)
可以使用摩尔投票算法,也就是每次去抵消不同数字。也就是去对拼消耗,最坏情况就是自己的这一半消耗剩余的,好的情况就是他们自己也会去消耗。

例如:

输入:{1,2,1,3,1,1,2,1,5}

序号也表明了数组的下标
0.从第一个数字1开始,我们想要把它和一个不是1的数字一起从数组里抵消掉,但是目前我们只扫描了一个1,所以暂时无法抵消它,把它加入到array,array变成了{1},result由于没有抵消任何元素所以还是原数组{1,2,1,3,1,1,2,1,5}。
1.然后继续扫描第二个数,是2,我们可以把它和一个不是2的数字抵消掉了,因为我们之前扫描到一个1,所以array变成了{},result变成了{1,3,1,1,2,1,5}
2.继续扫描第三个数1,无法抵消,于是array变成了{1},result还是{1,3,1,1,2,1,5}
3.接下来扫描到3,可以将3和array数组里面的1抵消,于是array变成了{},result变成了{1,1,2,1,5}
4.接下来扫描到1,此时array为空,所以无法抵消这个1,array变成了{1},result还是{1,1,2,1,5}
5.接下来扫描到1,此时虽然array不为空,但是array里也是1,所以还是无法抵消,把它也加入这个array,于是array变成了{1,1}
6.接下来扫描到2,把它和一个1抵消掉,至于抵消哪一个1,无所谓,array变成了{1},result是{1,1,5}
7.接下来扫描到1,不能抵消,array变成了{1,1},result{1,1,5}
8.接下来扫描到5,可以将5和一个1抵消,array变成了{1},result变成了{1}至此扫描完成了数组里的所有数,result里剩了1,所以1就是大于一半的数组。

其实array中只有一种数,因为只有array为空或当前扫描到的数和array里的数字相同时才把这个数字放入array

所以代码实现起来,只需要一个变量来代表array中存放的数就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 public int Solution(int [] array) {
if(array.length == 0) return 0;
int num = 0;//保存次数(例如第7步中,有两个1,则次数为2)
int myarray = array[0];//保存数字
for(int i = 0; i < array.length; i++) {
//如果次数为0,保存数字,次数置为1
if(num == 0) {
myarray = array[i];
num = 1;
}
//次数不为1,当前数字与保存的数字相同时,次数加1
else if (array[i] == myarray) {
num++;
}
//当前数字与保存的数字不同时,次数减1
else if (array[i] != myarray) {
num--;
}
}
return myarray;
}

那么如何找出出现次数大于三分之一的数呢?
思路一样,但是需要保存两个数去抵消

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 public int Solution(int [] array) {
if(array.length == 0) return 0;
int num1 = 0;
int num2 = 0;
int res1 = array[0];
int res2 = array[1];
for(int i = 0; i < array.length; i++) {

if(num1 == 0 || array[i] == res1) {
res1 = array[i];
num1 += 1;
}

else if (num2 == 0 || array[i] == res2) {
res2 = array[i];
num2 += 1;
}

else{
num1--;
num2--;
}
}
//最终确定剩下的两个数是否大于三分之一
return myarray;
}

cycle_detection

发表于 2018-09-26

floyd’s cycle detecion
为什么找出环的算法是使用快慢指针呢,以下做了简单的推导

如图所示,假设从环的起点到环的入口点的距离为m, 快慢指针的相遇点的距离据入口点的距离为k。
环的长度设置为l
则有dist_fast = m + p l + k,此为快指针行走的距离,也就是起点到入口点的距离 + 任意圈数(p圈)的环的长度 + 快慢指针相遇的点到入口的距离k。
同理dist_slow = m + q
l + k。 dist_fast = dist_slow 2 (因为快指针速度是慢指针两倍)。 推导则有 l (p-2q) = m + k
p-2q是一个整数,l * int = m + k, 因此当找到了相遇点之后, 快指针从起点开始,每次移动一步,慢指针从相遇点开始,每次移动一步。快指针移动m步时,慢指针也移动了m步,此时刚好等于一个环的长度的整数倍,因此也就是环的入口点。

adapter

发表于 2018-09-21

适配器模式(类适配器),将220v电压转为5v

class Voltage220V{

public int output220V(){
    int src = 220;
    System.out.println("220v");
    return src;
}

}

阅读全文 »

Hexo搭建教程

发表于 2018-08-24 | 分类于 python , java , c++ , SQL , C

Hexo搭建教程

阅读全文 »

Hello World

发表于 2018-08-23

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

阅读全文 »
12
Jie

Jie

咸鱼就是我
15 日志
10 分类
10 标签
© 2020 Jie
|