算法时空 算法

算法时空第14讲 从纸笔演算到发现算法

最小值插入问题和Majority问题

Posted by Twany on July 27, 2019

最小值计算

问题：对于概率值集 P，取最小的两个值求和再放入到 P 中，直至 P 仅存唯一元素 1

思路

  1. 首先我们需要两个队列，第一个队列存放原概率集，第二个概率存放相加之和的和
  2. 计算之前，我们首先需要对队列A进行排序，使其按由小到大排列
  3. 开始求和，题目要求把每次最小的两个值求和，最小值有两种存在情况
    1. 存在于队列A
    2. 存在于队列B（相加之后的值）
  4. 对两个队列的首元素进行比较，最小的就是所有元素的最小值其一，另外一个元素同理
  5. 取得最小的两个值，并从原队列删除。然后把和再次存入队列B中，继续循环

所以，我们的问题就转化为比较两个队列的最小值，且这两个队列按由小到大已排好序

代码如下：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public class Album
{
    public static void main(String[] args) {
        //  队头删除，队尾插入
        //  offer 添加，poll 删除，peek查看头
        Queue<Double> queue = new LinkedList(); //原队列

        Queue<Double> newQ = new LinkedList();  //相加存放队列

        //添加元素
        queue.offer(0.0625);queue.offer(0.0625);queue.offer(0.125); queue.offer(0.125);
        queue.offer(0.0625);queue.offer(0.0625);queue.offer(0.125);queue.offer(0.125);


        for (int i = 0; i < queue.size()-1; i++) {
          //因为是Double类型，默认值为 0 的话需要进行类型转换
          Double first= Double.valueOf(0);Double second = Double.valueOf(0);
          
          //当queue队列不为空，取出首元素
          if(!queue.isEmpty()){
              first = queue.peek();
          }
          //当新队列为空，那么弹出，供第二个元素的取得
          if(newQ.isEmpty()){
              //弹出queue的首位，表示已经确定了最小数就是它
              queue.poll();
          }else if(newQ.peek() <= first || queue.isEmpty()) { //短路表达式，防止原队列为空，first无法赋值
              first = newQ.poll();
              //此处不弹出queue的first，因为最小数已转移至newQ中
          }else{
              //当newQ不为空，且已经确定了最小数就是queue的首位，弹出
              queue.poll();
          }

          //second 和 first同理
          if(!queue.isEmpty()){
              second = queue.peek();
          }
          if(newQ.isEmpty()){
              queue.poll();
          }else if(newQ.peek() <= second || queue.isEmpty()){
              second = newQ.poll();
          }else{
              queue.poll();
          }

          //将最小值插入到新队列
          newQ.offer(first+second);
        }
    }
}

Majority 问题

问题：集合中出现一半的数称为众数（过半数），如何求解

方法一（元素去重）

对数组进行元素去重，统计输出次数，寻找众数。复杂度为o(nlogn)，较高

方法二（蓄水池 || 消砖块）

关键：当一个序列中存在众数时，其占比肯定超过50%

思路
  1. 当池中元素为空（0），遇到新元素将其添加进来，并设为标记元素
  2. 当池中元素不为空
    1. 遇到相同元素：计数器+1
    2. 遇到不同元素：计数器-1
  3. 最后，对标记元素进行检验，看是否大于出现次数大于一半
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class Test {
    public static void main(String[] args) {

        int[] arr = {1,3,9,4,6,4,4,6,7,6,4,4,4,4,4,4};

        //蓄水池计数器
        int count = 0;
        int temp = arr[0];

        for (int i = 0; i < arr.length; i++) {
            //当蓄水池为空，元素加入，并设立记号元素
            if(count == 0){
                count++;
                temp = arr[i];
            }else{//蓄水池不为空的情况
                if(arr[i] == temp){ //新元素和池中元素相同
                    count++;
                }else{
                    count--;    //不同
                }
            }
        }

        //此时的count并不是众数的个数，而是已经被抵消之后的数量，所有我们应进行检验
        if(count == 0){
            System.out.println("无解");
        }else{
            count = 0;
            for (int i : arr) {
                if(temp == i){
                    count++;
                }
            }

            if( 2*count < arr.length ){
                System.out.println("不足一半，无解");
            }
        }
        System.out.println(temp + "是众数，出现了" + count + "次"); //输出 “4是众数，出现了9此”
    }
}
CATALOG