高分求救~~~~~~~~~~~~~~~~~~~~~~

Question

有一个字符串数组,每个元素由数字+','组成,如:
Ary[0]:='1,3,5,7,9,........'
Ary[0]:='2,3,5,8,10,........'
每个元素中包含的数字可能达到50w个
假设这个数组有100个元素
先要求能从数组中快速实现:
返回在数组中出现了80次以上的前10个数字
有没有什么方法能快速得到,否则按常规方法,这个速度巨慢.分不够再加,我现在只能输入100的上限.谢谢.

Answer 1

var
  a:array[1..50 * 10000] of integer;//假设最大的数字是50万begin
  FillChar(a,0); //将数组A清空
  某个数字n每出现一次将a[n]加一（ O(n) ）
  然后取a[n]中最大的10个数字。（O(n) ）
end;

Answer 2

最大的数字：可以采用动态数组，发现一个数字太大了就重新SetLength一下。
如果数字实在太大，就只能采用hash表的方式了。

Answer 3

// 用一个临时表 Table(a,b,c)来记录已经读取的数据的个数。a字段为数值,b字段为出现个数,c为当前数据是否取出。
procedure .......
var
  i: Integer;
  outs: String;
begin
  outs:='';
  for i:=0 to Max(Ary[0]) do
  begin
    if Ary[0] in [Table(a)]
    then Table(b)=Table(b)+1
    else Table(Insert Ary[0],1);
    if Table(b)>80 and Table(c)=0 
    then begin
           outs=outs+Table(a)+','; 
           Table(c)=1;
         end;    
  end;
end;

Answer 4

windindance(风舞轻扬) 
我用的方式和你的一样,是动态设置数组的长度,但是这样的速度还是很慢.
另外我想得到的是满足条件的前10是指的出现频率最高的10个数字.
期待大家继续.谢谢.

Answer 5

把我的代码贴一下,我用的常规方法,效率慢啊.
procedure GetPosCnt(sPosList:TWideStrings;var AryStatCnt:TAryInt);
var
  i,iPos,iVal:integer;
  sPosInfo:WideString;
begin
  for i:=0 to sPosList.Count-1 do
  begin
    sPosInfo:=trim(sPosList.Strings[i]);
    iPos:=Pos(',',sPosInfo);
    while iPos>0 do
    begin
      iVal:=strtoint(trim(copy(sPosInfo,1,iPos-1)));
      if iVal+1>length(AryStatCnt) then SetLength(AryStatCnt,iVal+1);
      AryStatCnt[iVal]:=AryStatCnt[iVal]+1;
      sPosInfo:=trim(copy(sPosInfo,iPos+length(','),length(sPosInfo)));
      iPos:=Pos(',',sPosInfo);
    end;
  end;
end;

Answer 6

if iVal+1>length(AryStatCnt) then 
   SetLength(AryStatCnt,iVal＋1);
                             --修改为 iVal ＋ 1024 等其他值，分配一次内存是很慢的sPosInfo:=trim(copy(sPosInfo,iPos+length(','),length(sPosInfo)));
这样的字符串操作可能会很慢。
有优化的余地。
可以先将其全部转换到数组中去。
例如：
sl := TStringList.Create;
sl.CommaText := sPosInfo;