问题一
问题描述
给出不同策略返回一序列数中的众数（出现次数不小于序列长度的一半），并分析
问题分析
最简单的算法是先对序列进行排序，然后选取$(n/2)$和$(n/2-1)$位置的元素，分别与序列初值和末尾进行比较，如果有其中一个元素相等，则该元素是众数
选取其中一个元素作为侯选数，众数是出现次数不小于序列长度的一半的数，根据鸽笼原理得到序列中的其他元素的个数少于众数的个数，依据上述原理，能够判断侯选数是否为众数，这就是摩尔投票算法的基本步骤。
使用$hashtable$来存储
算法分析
排序算法
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int temp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
int FindMajority1(int arr[], int n) {
quickSort(arr, 0, n - 1);
if (n % 2 == 0) {
if (arr[n / 2] == arr[0] || arr[n / 2] == arr[n - 1]) {
return arr[n / 2];
}
if (arr[n / 2 - 1] == arr[0] || arr[n / 2 - 1] == arr[n - 1]) {
return arr[n / 2 - 1];
}
}
else {
if (arr[n / 2] == arr[0] || arr[n / 2] == arr[n - 1]) {
return arr[n / 2];
}
}
}摩尔投票算法
int FindMajority1(int array[],int n) {
int count = 0;
int cur;
for (int i = 0; i < n; i++) {
if (count == 0) {
cur = array[i];
}
if (cur == array[i]) {
count++;
}
else {
count--;
}
}
if (n != 2 && cur == array[n - 1]) {
return INT_MAX;
}
else {
return cur;
}
}$hashtable$法
int FindMajority3(int arr[], int n) {
unordered_map<int, int> counts;
int maxCount = 0;
int mode = 0;
for (int i = 0; i < n; i++) {
counts[arr[i]]++;
if (counts[arr[i]] > maxCount) {
maxCount = counts[arr[i]];
mode = arr[i];
}
}
if (maxCount >= n / 2) {
return mode;
}
return INT_MAX;
}算法实现与分析
#include<iostream>
#include<unordered_map>
using namespace std;
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int temp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
int FindMajority1(int arr[], int n) {
quickSort(arr, 0, n - 1);
if (n % 2 == 0) {
if (arr[n / 2] == arr[0] || arr[n / 2] == arr[n - 1]) {
return arr[n / 2];
}
if (arr[n / 2 - 1] == arr[0] || arr[n / 2 - 1] == arr[n - 1]) {
return arr[n / 2 - 1];
}
}
else {
if (arr[n / 2] == arr[0] || arr[n / 2] == arr[n - 1]) {
return arr[n / 2];
}
}
}
int FindMajority2(int array[],int n) {
int count = 0;
int cur = INT_MAX;
for (int i = 0; i < n; i++) {
if (count == 0) {
cur = array[i];
}
if (cur == array[i]) {
count++;
}
else {
count--;
}
}
if (n != 2 && cur == array[n - 1]) {
return INT_MAX;
}
else {
return cur;
}
}
int FindMajority3(int arr[], int n) {
unordered_map<int, int> counts;
int maxCount = 0;
int mode = 0;
for (int i = 0; i < n; i++) {
counts[arr[i]]++;
if (counts[arr[i]] > maxCount) {
maxCount = counts[arr[i]];
mode = arr[i];
}
}
if (maxCount >= n / 2) {
return mode;
}
return INT_MAX;
}
int main() {
int array[] = { 1,1,1,2,3,4 };
int n = sizeof(array) / sizeof(array[0]);
cout << FindMajority1(array, n) << endl;
cout << FindMajority2(array, n) << endl;
cout << FindMajority3(array, n) << endl;
}实现：
针对方法一，使用快速排序，因此时间复杂度是$O(nlogn)$，空间复杂度是$O(logn)$；
针对方法二，遍历一次数组，时间复杂度是$O(n)$，空间复杂度是$O(1)$；
针对方法三，遍历一次数组，时间复杂度是$O(n)$，空间复杂度是$O(n)$。
问题二
问题描述
给出不同策略将偶数个元素形成的序列分成两个子序列$S_1$$、$$S_2$$，要求$$S_1$$、$$S_2$的和差值最大
问题分析
方法一是使用动态规划算法，使用一个二维数组$dp[i][j]$表示前i个元素中是否存在一些元素的和为j，通过动态规划的方式逐步地求出$dp$数组地所有制，在dp数组中找到一个满足条件的最大的j。如果$dp[n][j]$的值为true，S1的和为j，S2为sum-j，两者差为$sum-2j$。
方法二是使用暴力枚举法，例举出两子序列分别进行求和，比较不同子序列之差
算法实现与分析
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<vector<int>> MaxDifference(vector<int> nums) {
int n = nums.size();
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
}
vector<vector<int>> dp(n + 1, vector<int>((sum >> 1) + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= (sum >> 1); j++) {
dp[i][j] = dp[i - 1][j];
if (j >= nums[i - 1]) {
dp[i][j] |= dp[i - 1][j - nums[i - 1]];
}
}
}
int maxdiff = 0;
int index = 0;
for (int j = (sum >> 1); j >= 0; j--) {
if (dp[n][j]) {
maxdiff = sum - 2 * j;
index = j;
break;
}
}
vector<int> S1, S2;
int i = n;
int j = index;
while (i > 0 && j > 0) {
if (dp[i - 1][j]) {
i--;
}
else {
S1.push_back(nums[i - 1]);
j -= nums[i - 1];
i--;
}
}
for (int i = 0; i < n; i++) {
if (find(S1.begin(), S1.end(), nums[i]) == S1.end()) {
S2.push_back(nums[i]);
}
}
return { S1,S2 };
}
int main() {
vector<int> nums = { 1,6,5,11,3,2 };
vector<int> S1, S2;
int n = nums.size();
vector<vector<int>> result = MaxDifference(nums);
S1 = result[0];
S2 = result[1];
for (int i = 1; i < (n >> 1); i++) {
cout << S1[i] << " ";
}
cout << endl;
for (int i = 1; i < (n >> 1); i++) {
cout << S2[i] << " ";
}
cout << endl;
}该算法的时间复杂度是$O(n^2)$，针对元素较多的序列处理能力强
#include <iostream>
#include <vector>
using namespace std;
vector<int> findMaxDiffSubsequence(const vector<int>& nums) {
int n = nums.size();
int maxDiff = INT_MIN;
vector<int> maxS1, maxS2;
for (int i = 0; i < (1 << n); i++) {
int s1sum = 0, s2sum = 0;
vector<int> s1, s2;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
s1.push_back(nums[j]);
s1sum += nums[j];
} else {
s2.push_back(nums[j]);
s2sum += nums[j];
}
}
int diff = s1sum - s2sum;
if (diff > maxDiff) {
maxDiff = diff;
maxS1 = s1;
maxS2 = s2;
}
}
return maxDiff > 0 ? maxS1 : maxS2;
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6};
vector<int> subsequence = findMaxDiffSubsequence(nums);
for (int i = 0; i < subsequence.size(); i++) {
cout << subsequence[i] << " ";
}
cout << endl;
return 0;
}
暴力枚举法的时间复杂度是$O(n2^n)$，处理方法简单，能够保证结果的正确性，但是时间复杂度很高，针对长序列不适用
