怎样求出点最密集的区域？

leefurong

1.一维空间，有2E64（2的64次方）个位置。
2.有100个不同的元素element[100]，分布在上述的一维空间中。每个元素都可能有多个位置。比如element[0]的位置可能有：
89,200,24445,233481,87659213,...已知这个列表已经按顺序排列好了。
3.求一个位置，这个位置以后的连续1000个位置中，不同元素的个数最多。


typedef long long Position;//C99 promise long long to be at least 64 bit
typedef struct{
  Position pos;
  Position_List *Next;
}Position_List;

//怎样设计此函数，以获得最快速度？
//参数：total_element是总共元素的个数,比如上面说的100。
//参数：element是一个指针，指向这样的数组：
//数组共有total_element个元素；
//每个元素都是一个链表的头节点。这个链表上记录了相应element的所有位置。
//返回：求一个位置，在此位置之后field个位置中，含有最大数量的不同元素。
Position biggest_density(int total_element,Position_List element[],long long field);

//element定义：
Position_List element[100];

leefurong

如果可以的话，最好求出多个位置（返回Position_List），这些位置随后的区域内，含有的元素数量从多到少排列。

Sorehead

如果一定要查出精确的最多，我只想到穷举。

iamkey9

原帖由 leefurong 于 2007-8-3 07:38 发表
1.一维空间，有2E64（2的64次方）个位置。
2.有100个不同的元素element[100]，分布在上述的一维空间中。每个元素都可能有多个位置。比如element[0]的位置可能有：
89,200,24445,233481,87659213,...已知这个列 ...

彩票？

tyc611

思路：遍历各元素数组的位置链表，进行计数。利用一个有序链表（PL）来记录由各元素的链表的当前位置所构成的位置序列。
（1）初始化，利用每个数组元素的链表的第一个位置建立有序链表PL。在该有序链表PL中，从最小的位置开始计数，找出在规定的位置范围内的元素个数，把该最小位置和元素个数记录下来，分别记录为当前计数序列的计数及位置和当前最大计数及位置（如果个数为数组元素个数，则算法结束，返回结果），也同时记下该计数序列外的第一个元素的位置（这样就记录下了计数范围）。
（2）把最小位置从有序链表PL中摘出，将最小的位置所在元素的链表位置移向下一个链表元素，并将新的位置插入到有序链表PL中。在插入时如果新元素仍在计数序列范围内则计数不变，否则计数减一；并更新当前计数序列的最小位置。然后，查看是否能添加计数序列外的元素到新的序列中。如果能够添加，则计数相应增加，此时需要检查当前计数是否超过当前最大计数，如果超过，则需更新当前最大计数及位置（如果新的最大计数为数组元素个数，则算法结束，返回结果）。如果不能再添加，则重复（2）。
（3）算法的结束：在（2）中，如果某个元素的链表到达了表尾，则此链表不再出现在有序链表PL中；当有序链表PL中的每一个元素都出现在计数序列中时，算法结束，返回当前的最大计数及位置。