关于数据结构:改进for循环时间复杂度的一种办法

41次阅读

共计 764 个字符,预计需要花费 2 分钟才能阅读完成。

找到 n 个数中两个数之和为 7 的对数

//(相比两层 for 循环工夫复杂度仅为 O(N) 的改良算法 ) 
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<stack> 
#include<set>
#include<map> 
#include<vector> 
using namespace std;
int main(){
    int n;// 要输出 n 个数来找和为 7 的数的数对 
    scanf("%d",&n);
    long long num[20];// 定义一个数组去存 %7 取余后余数为 i 的个数,20 是随便定的,>= 7 就行,因为任何数对 7 取余都小于 7 
    for(int i = 0; i < 20; i++){num[i] = 0;// 初始化一下,%7 余数为 i 的个数都是 0 
    }
    for(int i = 1; i <= n; i++){
        int x;// 输出 n 个数 
        scanf("%d",&x);
        num[x%7]++;// 记录余数为某个数 i 的个数,更新对应的 num[i] 的值来记录 
    } 
    long long sum = 0;
    sum += (num[0] *(num[0] - 1)/2);// 对 7 取余为 0 的比拟非凡(因为 14+14,7+ 7 等满足条件但却不是一对数 (应为不等的一对数))// 故满足条件的数是 7,14,21 等排列组合失去的个数为 n *(n-1)/2 
    sum += (num[1] * num[6]);// 对 7 取余为 1 的个数与对 7 取余为 6 的个数相乘失去 1 和 6 总对数(对 7 取余为 1 的数与对 7 取余为 6 的数相加必定是 7 的倍数)sum += (num[2] * num[5]);// 同理 
    sum += (num[3] * num[4]);// 同理
    printf("%lld\n",sum); 
    return 0;
} 

正文完
 0