一、找一找
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数
输入描述:
第一行输入一个n
接下来一行输入n个正整数a
i
输出描述:
输出符合条件个数
示例1
输入
5 1 2 3 4 5
输出
2
说明
5个数中1和2符合条件，1是后面每个数的因子，2是4的因子
第一遍写出来的程序，运行超时。
#include "stdafx.h"
#include<iostream>
using namespace std;
int search(int *array, int *flag, int n) {
int count = 0;
for (int i = 0; i<n; i++) {
for (int j = 0; j<n; j++) {
if (flag[j] != 1 && array[j] / array[i] > 1 && array[j] % array[i]==0)
{
count++;
flag[i] = 1;
break;
}
}
}
return count;
}
int main() {
int n;
cin >> n;
//数组原来可以这么初始化
int *array;
int *flag;
array = (int *)malloc(sizeof(int)*n);
flag = (int *)malloc(sizeof(int)*n);
for (int j = 0; j<n; j++) {
cin >> array[j];
}
int answer = search(array, flag, n);
cout << answer << endl;
return 0;
}思考：超时问题应该出自于双层for循环，如果先把数组排序，则可以用一层for循环来查找结果。
下面代码中的知识点：
1、快速排序之前将数组乱序的库函数
2、快速排序
#include "stdafx.h"
#include<iostream>
#include<algorithm>
using namespace std;
int search(int *array, int *flag, int n) {
int count = 0;
for (int i = 0; i<n; i++) {
for (int j = 0; j<n; j++) {
if (flag[j] != 1 && array[j] / array[i] > 1 && array[j] % array[i] == 0)
{
count++;
flag[i] = 1;
break;
}
}
}
return count;
}
//快速排序
void quickSort(int s[], int l, int r)
{
if (l< r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
// 从右向左找第一个小于x的数
while (i < j && s[j] >= x)
j--;
if (i < j)
s[i++] = s[j];
// 从左向右找第一个大于等于x的数
while (i < j && s[i]< x)
i++;
if (i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
int main() {
int n;
cin >> n;
//数组原来可以这么初始化
int *array;
int *flag;
array = (int *)malloc(sizeof(int)*n);
flag = (int *)malloc(sizeof(int)*n);
for (int j = 0; j<n; j++) {
cin >> array[j];
}
//打乱数组元素
int* a_begin = array;
int* a_end = array + n;
random_shuffle(a_begin, a_end);
/*for (int* p = a_begin; p != a_end; p++)
{
cout << *p << "\t";
}*/
//快速排序
quickSort(array, 0, n - 1);
/*for (int k = 0; k<n; k++)
cout << array[k] << ",";*/
int answer = search(array, flag, n);
cout << answer << endl;
return 0;
}
上面的代码依旧没有解决时间复杂度的问题，于是我搜了这道题的标准答案，在答案中又学到了新的知识
1、
#include<bits/stdc++.h> 包含了目前c++所包含的所有头文件，所有的代码只要用了这个头文件就不再写其他头文件了
2、
1e6 表示1*10^6
3、
a[m]++
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+3;
int a[N];
int main()
{
int n, i, m, j, sum = 0;
cin>>n;
for(i = 1; i <= n; i++)
{
scanf("%d", &m);
a[m]++;
}
for(i = 1; i <= n; i++)
{
if(a[i] > 0)
{
for(j = 2; i*j <N; j++)
{
if(a[i*j] > 0)
{
sum += a[i];
break;
}
}
}
}
printf("%d\n", sum);
return 0;
}
