我遇到了一个问题:
给定一个数组，查找max其中Count对于数组中的元素定义为no。
例子:max数组[2,2,2,5,6,8,9,9]中的count为4，因为6或8可以被2、2、2和它们自己整除。
我的方法是:
- 排序数组
- 从这个数组中创建一个集合(在某种程度上，即使这个集合也是按非降序排序的)
- 取另一个数组，其中数组索引初始化为no。元素在原始数组中出现的次数。例子:在上面的例子中，元素'2'出现了三次，因此索引'2-1'在这个新数组中被初始化为3，索引'9-1'将被初始化为2，因为'9'在这个数组中出现了两次。
- 使用两个循环，我检查集合中最大(从最大移动到最小)元素与集合中最小(从最小移动到最大)元素的可整除性。
条件
1 <= arr[i] <= 10000
1 <= i <= 10000
#include <stdio.h>
#include <stdlib.h>
#include<limits.h>
int cmp(const void *a, const void *b)
{
return (*(int*)a - *(int*)b);
}
void arr_2_set(int *arr, int arr_size,int *set, int *len)
{
int index = 0;
int set_len = 0;
int ele = INT_MIN;
qsort(arr,arr_size,sizeof(int),cmp);
while(index < arr_size)
{
if(ele != arr[index])
{
ele = arr[index];
set[set_len] = ele;
set_len++;
}
index++;
}
*len = set_len;
}
int main(void)
{
int arr[]={2,2,2,5,6,8,9,9}; //array is already sorted in this case
int size = sizeof(arr)/sizeof(arr[0]);
int set[size];
int index = 0;
int set_len = 0;
arr_2_set(arr, size, set, &set_len); //convert array to set - "set_len" is actual length of set
int rev = set_len-1; //this will point to the largest element of set and move towards smaller element
int a[100000] = {[0 ... 99999] = 0}; //new array for keeping the count
while(index<size)
{
a[arr[index] -1]++;
index++;
}
int half;
int max=INT_MIN;
printf("set len =%dnn",set_len);
for(;rev>=0;rev--)
{
index = 0;
half = set[rev]/2;
while(set[index] <= half)
{
if(set[rev]%set[index] == 0)
{
a[set[rev] -1] += a[set[index]-1]; //if there are 3 twos, then 3 should be added to count of 8
//printf("index =%d rev =%d set[index] =%d set[rev] =%d count = %dn",index,rev,set[index],set[rev],a[set[rev] -1]);
}
if(max < a[set[rev]-1])
max = a[set[rev]-1];
index++;
}
}
printf("%d",max);
return 0;
}
现在我的问题是如何加快这个程序?我能够通过9/10个测试用例——对于第10个测试用例(隐藏的)，它显示了"时间限制超出">。
- 对于创建集合和查找计数-使用单个
while循环，当数组的大小很大时，使用单个循环将会很重要。 - 在有两个嵌套循环的后半部分，不要从最大元素到最小元素。从最小元素到最大元素while检查哪个索引比当前元素低的最大元素可以划分该元素，将该元素的计数添加到当前元素的计数(使用
set[i]/2逻辑在这里仍然有效)。这样你就可以避免很多分歧。例如:如果设置为{2,3,4,8}，在这种情况下，让我们说你的当前位置是8，然后你向下直到最大的元素小于或等于8，可以除以8，并将其计数添加到当前元素(8)计数。
对于第10个测试用例(隐藏的)，它显示"Time Limit Exceeded">。
这可能意味着需要一种更省时的算法。
张贴的一个，首先排序数组(使用qsort)，然后只复制唯一值到另一个数组，set。
考虑到可能值的约束，实现计数排序算法可能更便宜。
最后一部分搜索股息的最大数量，然后可以使用额外的数组作为筛子来实现。
#include <stdio.h>
enum constraints {
MAX_VALUE = 10000
};
int count_dividends(size_t n, int const *arr)
{
// The actual maximum value in the array will be used as a limit.
int maxv = 0;
int counts[MAX_VALUE + 1] = {0};
for (size_t i = 0; i < n; ++i)
{
if ( counts[arr[i]] == 0 && arr[i] > maxv )
{
maxv = arr[i];
}
++counts[arr[i]];
}
// Now, instead of searching for the dividends of an element, it
// adds the number of factors to each multiple.
// So, say there are two elements of value 3, it adds 2 to all
// the multiples of 3 in the total array.
int totals[MAX_VALUE + 1] = {0};
int count = 0;
// It starts from 2, it will add the numbers of 1's once, at the end.
for (int i = 2; i <= maxv; ++i)
{
// It always skips the values that weren't in the original array.
if ( counts[i] != 0 )
{
for ( int j = 2 * i; j <= maxv; j += i)
{
if ( counts[j] != 0 )
totals[j] += counts[i];
}
if ( counts[i] + totals[i] > count )
{
count = counts[i] + totals[i];
}
}
}
return count + counts[1];
}
int main(void)
{
{
int a[] = {2, 4, 5, 1, 1, 6, 14, 8, 2, 12, 1, 13, 10, 2, 8, 5, 9, 1};
size_t n = (sizeof a) / (sizeof *a);
// Expected: 10, because of 1 1 1 1 2 2 2 4 8 8
printf("%dn", count_dividends(n, a));
}
{
int a[] = {2, 4, 5, 2, 7, 10, 9, 8, 2, 4, 4, 6, 5, 8, 4, 7, 6};
size_t n = (sizeof a) / (sizeof *a);
// Expected: 9, because of 2 2 2 4 4 4 4 8 8
printf("%dn", count_dividends(n, a));
}
}