寻找主元素

2013

  1. 已知一个整数序列A=(a0, a1,… an-1)其中0 ≤ ai ≤ n，若存在ap1=ap2= … =apm=x且 m > n/2则称x为A的主元素。
  2. 假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法找出A的主元素（存在输出该元素否则输出-1）。
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
52
53
54
55
56
57
58
59
#include "preset.h"
#include <map>

//主元素抵消思路
bool half(SqList sql, int &res) {
    int temp = sql.elem[0];
    int count = 1;

    for (int i = 1; i < sql.length; ++i) {
        if (sql.elem[i] == temp) count++;
        else {
            if (count > 0) {
                count--;
            }
            else {
                temp = sql.elem[i];
                count = 1;
            }
        }
    }

    int k = 0;
    for (int i = 0; i < sql.length; ++i) {
        if (sql.elem[i] == temp) ++k;
    }
    if (k > (sql.length / 2)) {
        res = temp;
        return true;
    }
    return false;
}

//哈希map思路
bool hashmapp(SqList sql, int &res) {
    map<int, int> mp;
    for (int i = 0; i < sql.length; ++i) mp[sql.elem[i]]++;
    int temp, count = 0;

    for (auto v:mp) {
        if (v.second > count) {
            temp = v.first;
            count = v.second;
        }
    }
    if (count > sql.length/2) {
        res = temp;
        return true;
    }
    return false;
}

int main() {
    //SqList sql = {{0, 5, 5, 3, 5, 7, 5, 5}, 8};
    SqList sql = {{0, 5, 5, 3, 5, 1, 5, 7}, 8};
    cout << "current List:" << endl; print(sql);
    int res = -1; half(sql, res);
    cout << "major element : " << res << endl;
    return 0;
}

13.寻找最小正整数【2018】

给定一个含n个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。

image-20230703093433045

1.试解

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
52
53
54
55
56
57
58
59
60
//烂代码
#include "preset.h"

int listMax(SqList sql) {
    int res = sql.elem[0];
    for (int i = 1; i < sql.length; ++i) {
        if (sql.elem[i] > res) {
            res = sql.elem[i];
        }
    }
    return res;
}

int listMin(SqList sql) {
    int res = sql.elem[0];
    for (int i = 1; i < sql.length; ++i) {
        if (sql.elem[i] < res) {
            res = sql.elem[i];
        }
    }
    return res;
}

//listDelete删除指定元素
void listDelete(SqList &sql, int x) {
    int k = 0;
    for (int i = 0; i < sql.length; ++i) {
        if (sql.elem[i] == x) {
            k++;
        } else {
            sql.elem[i - k] = sql.elem[i];
        }
    }
    sql.length = sql.length - k;
}

int maxPositiveInt(SqList sql) {
    int min = listMin(sql);
    int max = listMax(sql);
    int i = 1;
    while (sql.length) {
        if (i < min) break;
        if (min == i) i++;
        //删除sql中的最小元素
        print(sql);
        listDelete(sql, min);
        //重新确定最小元素
        min = listMin(sql);
    }
    if (min == max) return max + 1;
    else return i;
}

int main() {
    //SqList sql = {{-5, 4, 1, 2, 3, 5, 6}, 7};
    //SqList sql = {{-5, 3, 2, 3}, 4};
    SqList sql = {{-5, -3, 1, 2, 3}, 5};
    cout << maxPositiveInt(sql);
    return 0;
}

2.参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//寻找数组中未出现的、最小的正整数
//设计一个在时间上尽可能高效的算法，找出数组中 未出现的 最小的 正整数

#include "preset.h"

int findMin(SqList sql) {
    int n = sql.length;
    int mark[n + 2] = {0};
    for (int i = 0; i < n; ++i) {
        if (sql.elem[i] > 0 && sql.elem[i] <= n + 1) mark[sql.elem[i]] = 1;
    }
    for (int i = 1; i <= n + 1; ++i) {
        if (mark[i] == 0) return i;
    }
    return -1;
}

int main() {
    //SqList sql = {{-5, 4, 1, 2, 3, 5, 6}, 7};
    SqList sql = {{-5, 3, 2, 3}, 4};
    //SqList sql = {{-5, -3, 1, 2, 3}, 5};
    cout << findMin(sql);
    return 0;
}

14.寻找三元组的最小距离【2020】

  1. 定义三元组(a,b,c)的距离为D=|a-b|+|b-c|+|c-a|，给定3个非空整数集合S1、S2、S3按照升序分别存储在3个数组中。
  2. 请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)中的最小距离。

image-20230703093452787

1.枚举

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
/*
给定3个非空整数集合S1、S2和S3、按照升序分别存储在3个数组中
设计一个算法计算出 所有可能的三元组 中的最小距离
*/
#include "preset.h"

#define Max 0x7fffffff

//计算绝对值
int cul(int a, int b, int c) {
    return abs(a - b) + abs(b - c) + abs(c - a);
}

//判定是否为最小值
bool isMin(int a, int b, int c) {
    if (min(a, min(b, c)) == a) {
        return true;
    }
    return false;
}

int minTri(SqList a, SqList b, SqList c) {
    int i = 0, j = 0, k = 0;
    int ans = Max;
    while (i < a.length && j < b.length && k < c.length && ans >= 0) {
        int temp = cul(a.elem[i], b.elem[j], c.elem[k]);
        if (temp < ans) ans = temp;
        if (isMin(a.elem[i], b.elem[j], c.elem[k])) i++;
        else if (isMin(b.elem[i], a.elem[j], c.elem[k])) j++;
        else k++;
    }
    cout << "min_i = " << i << " min_j = " << j << " min_k = " << k << endl;
    return ans;
}

int main() {
    SqList a = {{-1, 0, 9}, 3};
    SqList b = {{-25, -10, 10, 11}, 4};
    SqList c = {{2, 9, 17, 30, 41}, 5};
    cout << minTri(a, b, c) << endl;
    return 0;
}

2.暴力法

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
//暴力法
#include "preset.h"

//计算绝对值
int cul(int a, int b, int c) {
    return abs(a - b) + abs(b - c) + abs(c - a);
}

//暴力循环法
int minTri(SqList a, SqList b, SqList c) {
    int min_i, min_j, min_k;
    int min = cul(a.elem[0], b.elem[0], c.elem[0]);
    for (int i = 0; i < a.length; ++i) {
        for (int j = 0; j < b.length; ++j) {
            for (int k = 0; k < c.length; ++k) {
                int temp = cul(a.elem[i], b.elem[j], c.elem[k]);
                if (temp < min) {
                    min = temp;
                    min_i = i;
                    min_j = j;
                    min_k = k;
                }
            }
        }
    }
    cout << "min_i = " << min_i << " min_j = " << min_j << " min_k = " << min_k << endl;
    return min;
}

int main() {
    SqList a = {{-1, 0, 9}, 3};
    SqList b = {{-25, -10, 10, 11}, 4};
    SqList c = {{2, 9, 17, 30, 41}, 5};
    cout << minTri(a, b, c) << endl;
    return 0;
}