算法题T3

本文最后更新于：3 个月前

输入一个整型数组，找出其中出现次数超过一半以上的元素，输出该元素，例如：输入[1,5,9,5,5,4,8,5,5]，输出：5

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
/*
 遍历数组，保存两个值，一个是数组中的数组，一个是次数
 当遍历下一个数字时，如果下一个数字和当前保存的数字相同，则次数加1，如果不同则次数减1，
 如果次数为0，则需要保存下一个数字，并把次数设为1
 由于要找的数字出现的次数比其他所有数字出现的次数之和还要多，所以要找的数字肯定是最后一次把次数设为1的那个数字
 */

let input: [Int] = [1, 5, 9, 5, 5, 4, 8, 5, 5];
print("输入：", input);

var n: Int!
var c = 0

for i in 0 ..< input.count {
    let e = input[i];
    if i == 0 {
        n = e
        c = 1
    } else {
        if n == e {
            c += 1
        } else {
            c -= 1
            if c == 0 {
                n = e
                c = 1
            }
        }
    }
}
print("输出：" + String(n));
1
2
输入： [1, 5, 9, 9, 9, 9, 9, 9, 9, 9, 9, 5, 5, 4, 8, 5, 5]
输出：9