2.2.3, 12
- 找重复元素，且该元素个数要超过数组的一半，所以一个数组最多只有一个主元素
- 暴力，就是拿空间换时间，类似桶排序
- 开一个新数组，新数组的下标对应元素值，值对应元素个数（因为数的范围是确定的）
- 时间复杂度O(n)，空间复杂度O(n)
int find_main(SqList list) { // 1.初始化一个全为0的数组 int tmp[list.length] = {0}; // 2.新数组的下标对应元素值，值对应元素个数 for (int i = 0; i < list.length; i++) { tmp[list.data[i]]++; } // 3.遍历找出主元素 for (int i = 0; i < list.length; i++) { if (tmp[i] > list.length / 2 ) return i; } // 4.没找到返回-1 return -1; } 复制代码
- 第二种方法：我们先排好序再找主元素
- 记录每个元素出现的次数，如果后面的数不是重复元素，就判断当前元素是否为主元素
- 因为用了快排，时间复杂度O(nlog2n)，空间复杂度O(logn)
- 总分13分，这个解最高可以拿11分，所以不要强求最优解
int find_main2(SqList list) { // 1.快排 sort(list.data, list.data+list.length); // 2.记录每个元素出现的次数，找到主元素 int cnt = 1; for (int i = 0; i < list.length - 1; i++) { if (list.data[i+1] == list.data[i]) { cnt++; } else { if (cnt > list.length / 2) return list.data[i]; cnt = 1; } } return -1; } 复制代码
- 这道题考试的时候（
应该大概也许）可以不写跟题目无关的排序的具体实现 - 因为快排每次递归需要的空间是固定的，递归层数即为空间复杂度，故快排的平均空间复杂度为O(log2n)
- 快排的实现如下：
void quick_sort(int l, int r) { if (l == r) return; int x = a[(l+r)/2]; // 1.枢纽元素 // 2.分成两块 int i = l-1, j= r+1; while (i < j) { while (a[++i] < x); // 找到左边比x大的元素 while (a[--j] > x); // 找到右边比x小的元素 if (i < j) swap(a[i], a[j]); // 互换 } // 3.递归 quick_sort(l, j); quick_sort(j+1, r); } 复制代码
- 最优解，对对碰
- 因为主元素个数要超过数组的一半，它就可以抵掉所有其他元素且有剩余
- 时间复杂度O(n)，空间复杂度O(1)
int find_main3(SqList list) { int c, cnt = 1; c = list.data[0]; // 1.选定候选主元素 for (int i = 1; i < list.length; i++) { if (list.data[i] == c) cnt++; else { if (cnt > 0) { cnt--; } else { c = list.data[i]; cnt = 1; } } } // 2.统计实际数量 if (cnt > 0) { cnt = 0; for (int i = 0; i < list.length; i++) if (list.data[i] == c) cnt++; } // 3.确认主元素 if (cnt > list.length / 2) return c; return -1; }
