Z
zlq
Unregistered / Unconfirmed
GUEST, unregistred user!
怎样得到数组中相同的元素.
要尽可能的快.
要尽可能的快.
A
Another_eYes
Unregistered / Unconfirmed
GUEST, unregistred user!
先排序再找
L
LeeChange
Unregistered / Unconfirmed
GUEST, unregistred user!
精辟
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
排序得费用太大了吧？n*(n-1)/2
可以先建立一个连表数组， 然后扫描数据
依次插入链表， 这样得代价是n
算法每问题吧？
想一想打拖拉机是怎样分牌。
type
Pnode=^node;
node=record
i:integer //数组下表
next
node;
end;
var
b:array[1..n] of pnode ;
可以先建立一个连表数组， 然后扫描数据
依次插入链表， 这样得代价是n
算法每问题吧？
想一想打拖拉机是怎样分牌。
type
Pnode=^node;
node=record
i:integer //数组下表
next
node;end;
var
b:array[1..n] of pnode ;
N
nuke
Unregistered / Unconfirmed
GUEST, unregistred user!
拖拉机？？？？
怎么个打法？？
也许我会，但名字不同.....???
怎么个打法？？
也许我会，但名字不同.....???
J
Jacky Zhao
Unregistered / Unconfirmed
GUEST, unregistred user!
可不可以把程序例子给我
P
popeye
Unregistered / Unconfirmed
GUEST, unregistred user!
拖拉机,又名 双升级
链表的插入等操作参照 数据结构
链表的插入等操作参照 数据结构
A
Another_eYes
Unregistered / Unconfirmed
GUEST, unregistred user!
快速排序+二分法搜索的效率应该是最高的了. 只要找到一个相符的
就等于找到所有的了(排序之后相同的数据都在一起的).
具体算法delphi的demos里都有.
就等于找到所有的了(排序之后相同的数据都在一起的).
具体算法delphi的demos里都有.
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
快速排序是块, 可是人家要你排序了吗?
排序是不用动脑子, 只用本力气方法.
在数据量小的情况下, 可以采用
但在要求效率的时候, 就值得商榷了.
打个比方, 现有四付牌混在一起, 要把他分成两付两幅
好打拖拉机, 你会怎么做?
从A 到 K 先排序? 不太可能吧?
你是不是不用关心大小, 只把相同的发到一堆?
明白了?
举个例子
12 8 23 9 8 34 12 8 12
用上面的方法,结果是
12 12 12
8 8 8
23
9
34
只是上一贴子中链表中保存的是下表而已.处理起纪录来
更方便 一些.
最后一点, 无论何时, 排序都是一种费时费力的事情.
除非是没有别的方法, 或数据访问十分频繁.
排序是不用动脑子, 只用本力气方法.
在数据量小的情况下, 可以采用
但在要求效率的时候, 就值得商榷了.
打个比方, 现有四付牌混在一起, 要把他分成两付两幅
好打拖拉机, 你会怎么做?
从A 到 K 先排序? 不太可能吧?
你是不是不用关心大小, 只把相同的发到一堆?
明白了?
举个例子
12 8 23 9 8 34 12 8 12
用上面的方法,结果是
12 12 12
8 8 8
23
9
34
只是上一贴子中链表中保存的是下表而已.处理起纪录来
更方便 一些.
最后一点, 无论何时, 排序都是一种费时费力的事情.
除非是没有别的方法, 或数据访问十分频繁.
A
Another_eYes
Unregistered / Unconfirmed
GUEST, unregistred user!
有趣的理论.
>>可以先建立一个连表数组， 然后扫描数据
>>依次插入链表， 这样得代价是n
^^^^^^^^
请问如何个依次法? 不也是排序吗? 代价是n吗? 动动脑子吧.
^^^^
将原始数据搬到链表中的开销是n, 但要搬到链表中正确的位置呢?
不另外得n次扫描链表吗(每搬一个扫描一次)? 这个开销是多少?
实在搞不动为什么您老是说什么拖拉机?
问题是什么看清了吗?
就拿你举的例子来说吧:
>> 从A 到 K 先排序? 不太可能吧?
>> 你是不是不用关心大小, 只把相同的发到一堆?
不是废话吗? 发到一堆才能解决zlq的问题-->找到相同的元素嘛, 因为排
序后相同的都在一起.
>> 举个例子
>> 12 8 23 9 8 34 12 8 12
>> 用上面的方法,结果是
>> 12 12 12
>> 8 8 8
>> 23
>> 9
>> 34
这是你的方法得到的结果吧? 如果要找34, 只有顺序搜索到最后一个时才
能找到, 没有任何的优化方法, 假设数据量极大的话, 您的方法效率何在?
如果用我的方法, 排序后(我的排序也相当与您的将原始数据搬到链表中的
步骤, 而且我可以用经典的快速排序法, 速度比你的顺序搬动--相当于冒泡
排序法--效率高几倍)得到的结果是:
888
9
12 12 12
23
34
然后我可以用经典的二分法查找, 效率又是您顺序查找的几倍, 而且数据量
越大, 效率也越高.
>> 最后一点, 无论何时, 排序都是一种费时费力的事情.
>>除非是没有别的方法, 或数据访问十分频繁.
最后说一点, 无论何时, 顺序查找都是一种最费时的事情, 当然最简单,
不用动脑子.
但您不能因为它最简单, 就否定其他方法的效率比这个高.
排序的确是一种费时费力的事, 但费的这点时在以后查找中可以几倍节约
下来.
费的这点力可以提高您的编程水平.
>>可以先建立一个连表数组， 然后扫描数据
>>依次插入链表， 这样得代价是n
^^^^^^^^
请问如何个依次法? 不也是排序吗? 代价是n吗? 动动脑子吧.
^^^^
将原始数据搬到链表中的开销是n, 但要搬到链表中正确的位置呢?
不另外得n次扫描链表吗(每搬一个扫描一次)? 这个开销是多少?
实在搞不动为什么您老是说什么拖拉机?
问题是什么看清了吗?
就拿你举的例子来说吧:
>> 从A 到 K 先排序? 不太可能吧?
>> 你是不是不用关心大小, 只把相同的发到一堆?
不是废话吗? 发到一堆才能解决zlq的问题-->找到相同的元素嘛, 因为排
序后相同的都在一起.
>> 举个例子
>> 12 8 23 9 8 34 12 8 12
>> 用上面的方法,结果是
>> 12 12 12
>> 8 8 8
>> 23
>> 9
>> 34
这是你的方法得到的结果吧? 如果要找34, 只有顺序搜索到最后一个时才
能找到, 没有任何的优化方法, 假设数据量极大的话, 您的方法效率何在?
如果用我的方法, 排序后(我的排序也相当与您的将原始数据搬到链表中的
步骤, 而且我可以用经典的快速排序法, 速度比你的顺序搬动--相当于冒泡
排序法--效率高几倍)得到的结果是:
888
9
12 12 12
23
34
然后我可以用经典的二分法查找, 效率又是您顺序查找的几倍, 而且数据量
越大, 效率也越高.
>> 最后一点, 无论何时, 排序都是一种费时费力的事情.
>>除非是没有别的方法, 或数据访问十分频繁.
最后说一点, 无论何时, 顺序查找都是一种最费时的事情, 当然最简单,
不用动脑子.
但您不能因为它最简单, 就否定其他方法的效率比这个高.
排序的确是一种费时费力的事, 但费的这点时在以后查找中可以几倍节约
下来.
费的这点力可以提高您的编程水平.
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
哇... 我快要体无完肤了......
这个问题似乎已经很明白了, 不过还是想为自己辩护两句:
我忘了说明白了, 我的连标是散列存储, 访问效率为1
而切, 我从没说过要插入排序, 我的意思是
每一个相同的数值对应一个链表, 而链表的的头指针
放在数组(散列表)里面. (以空间换时间)
这样看来, 还是快速排序简单一些.
这个问题似乎已经很明白了, 不过还是想为自己辩护两句:
我忘了说明白了, 我的连标是散列存储, 访问效率为1
而切, 我从没说过要插入排序, 我的意思是
每一个相同的数值对应一个链表, 而链表的的头指针
放在数组(散列表)里面. (以空间换时间)
这样看来, 还是快速排序简单一些.
A
Another_eYes
Unregistered / Unconfirmed
GUEST, unregistred user!
不好意思, 说了这么多都是空话. 下面给出个完整的例子.
procedure SortDemo;
var
A: array [0..50000] of Integer;
// 要查找的数据
B: array [0..50000] of Integer;
// A中的下标
C: TList;
// 存放找到的结果
i: Integer;
Lo, Hi, Mid, Swp: Integer;
s: string;
procedure QuickSort(iLo, iHi: Integer);
begin
Lo := iLo;
Hi := iHi;
Mid := A[(B[Lo]+B[Hi]) div 2];
repeat
while A[B[Lo]] < Middo
Inc(Lo);
while A[B[Hi]] > Middo
Dec(Hi);
if Lo <= Hi then
begin
Swp := B[Lo];
B[Lo] := B[Hi];
B[Hi] := Swp;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then
QuickSort(iLo, Hi);
if Lo < iHi then
QuickSort(Lo, iHi);
end;
begin
// 初始化
randomize;
for i := 0 to 50000do
begin
a := random(50000);
b := i;
end;
// 排序
quicksort(0, 50000);
// 查找
i := 12774;
// 假设查找有多少个12774及具体位置, 结果坐标存放在C中
C := TList.Create;
Lo := 0;
Hi := 50000;
while Lo <= Hido
begin
Mid := (Lo + Hi) shr 1;
if A[B[Mid]] < i then
Lo := Mid + 1
else
begin
Hi := Mid - 1;
if A[B[Mid]] = i then
// 找到了
begin
C.add(Pointer(B[Mid]));
Lo := Mid - 1;
while (Lo >= 0) and (A[B[Lo]] = i)do
begin
C.Add(pointer(B[Lo]));
dec(Lo);
end;
Lo := Mid + 1;
while (Lo <= 50000) and (A[B[Lo]] = i)do
begin
C.Add(Pointer(B[Lo]));
Inc(Lo);
end;
end;
end;
end;
if C.Count = 0 then
showmessage('找不到.')
else
begin
showmessage(format('总共有 %d 项符合.', [c.count]));
s := '';
for Lo := 0 to c.count - 1do
s := s + ' ' + IntToStr(Integer(c.items[Lo]));
showmessage('它们分别为第 '+ s + '项');
end;
c.free;
end;
procedure SortDemo;
var
A: array [0..50000] of Integer;
// 要查找的数据
B: array [0..50000] of Integer;
// A中的下标
C: TList;
// 存放找到的结果
i: Integer;
Lo, Hi, Mid, Swp: Integer;
s: string;
procedure QuickSort(iLo, iHi: Integer);
begin
Lo := iLo;
Hi := iHi;
Mid := A[(B[Lo]+B[Hi]) div 2];
repeat
while A[B[Lo]] < Middo
Inc(Lo);
while A[B[Hi]] > Middo
Dec(Hi);
if Lo <= Hi then
begin
Swp := B[Lo];
B[Lo] := B[Hi];
B[Hi] := Swp;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then
QuickSort(iLo, Hi);
if Lo < iHi then
QuickSort(Lo, iHi);
end;
begin
// 初始化
randomize;
for i := 0 to 50000do
begin
a := random(50000);
b := i;
end;
// 排序
quicksort(0, 50000);
// 查找
i := 12774;
// 假设查找有多少个12774及具体位置, 结果坐标存放在C中
C := TList.Create;
Lo := 0;
Hi := 50000;
while Lo <= Hido
begin
Mid := (Lo + Hi) shr 1;
if A[B[Mid]] < i then
Lo := Mid + 1
else
begin
Hi := Mid - 1;
if A[B[Mid]] = i then
// 找到了
begin
C.add(Pointer(B[Mid]));
Lo := Mid - 1;
while (Lo >= 0) and (A[B[Lo]] = i)do
begin
C.Add(pointer(B[Lo]));
dec(Lo);
end;
Lo := Mid + 1;
while (Lo <= 50000) and (A[B[Lo]] = i)do
begin
C.Add(Pointer(B[Lo]));
Inc(Lo);
end;
end;
end;
end;
if C.Count = 0 then
showmessage('找不到.')
else
begin
showmessage(format('总共有 %d 项符合.', [c.count]));
s := '';
for Lo := 0 to c.count - 1do
s := s + ' ' + IntToStr(Integer(c.items[Lo]));
showmessage('它们分别为第 '+ s + '项');
end;
c.free;
end;
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
Another_eyes 兄 ,
不愿意再入了, 在你的上面改一下, 不会说我D版吧?
procedure SortDemo;
type
Pnode=^node;
node=record
num:integer;
nextnode;
end;
var
A: array [0..50000] of Integer;
// 要查找的数据
B: array [0..50000] of pnode;
// A中的下标
i,count:integer;
pnode;
procedure NoSort;
var pnode;
begin
for i:= 0 to 50000do
begin
new( p);
p^.num:=i;
p^.next:=b[a];
b[a]:=p;
end;
end;
begin
// 初始化
randomize;
for i := 0 to 50000do
begin
a := random(50000);
b := i;
end;
//分堆
Nosort(0, 50000);
// 查找
i := 12774;
// 假设查找有多少个12774及具体位置, 结果坐标存放在b中
if b=nil then
showmessage('找不到.')
else
begin
count:=0;s:='';p:=b;
while p<>nildo
begin
s := s + ' ' + IntToStr(Integer(p^.num));
p:=p^.next;inc(count);
end;
showmessage(format('总共有 %d 项符合.', [count]));
showmessage('它们为第 '+ s + '项');
end;
如果不再查找的化, 释放连标, 否则, 留待后用.
end;
不愿意再入了, 在你的上面改一下, 不会说我D版吧?
procedure SortDemo;
type
Pnode=^node;
node=record
num:integer;
next
node;end;
var
A: array [0..50000] of Integer;
// 要查找的数据
B: array [0..50000] of pnode;
// A中的下标
i,count:integer;
p
node;procedure NoSort;
var p
node;begin
for i:= 0 to 50000do
begin
new( p);
p^.num:=i;
p^.next:=b[a];
b[a]:=p;
end;
end;
begin
// 初始化
randomize;
for i := 0 to 50000do
begin
a := random(50000);
b := i;
end;
//分堆
Nosort(0, 50000);
// 查找
i := 12774;
// 假设查找有多少个12774及具体位置, 结果坐标存放在b中
if b=nil then
showmessage('找不到.')
else
begin
count:=0;s:='';p:=b;
while p<>nildo
begin
s := s + ' ' + IntToStr(Integer(p^.num));
p:=p^.next;inc(count);
end;
showmessage(format('总共有 %d 项符合.', [count]));
showmessage('它们为第 '+ s + '项');
end;
如果不再查找的化, 释放连标, 否则, 留待后用.
end;
A
Another_eYes
Unregistered / Unconfirmed
GUEST, unregistred user!
如果我改动一下初始话条件与查询值的话, 你的程序如何改能?
for i := 0 to 50000do
begin
a := random(1000000);
b := i;
end;
现在要查 60000 有几个的话... 嘿嘿. (我心不黑吧? 没random($7fffffff))
for i := 0 to 50000do
begin
a := random(1000000);
b := i;
end;
现在要查 60000 有几个的话... 嘿嘿. (我心不黑吧? 没random($7fffffff))
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
还说不黑 !
不过也没关系, 构造一个散列函数, 形成一个 a--b
的映射关系(不能一一对应也没关系,有各种防止碰撞
的办法)
不过, 这么一来, 省下来的代码又给搭进去了,
我承认, 你的方法更直接明了,一般人更容易理解
不过, 我的方法效率更高, 你也不得不承认.
握手言和吧 ....... I fule you.
不过也没关系, 构造一个散列函数, 形成一个 a--b
的映射关系(不能一一对应也没关系,有各种防止碰撞
的办法)
不过, 这么一来, 省下来的代码又给搭进去了,
我承认, 你的方法更直接明了,一般人更容易理解
不过, 我的方法效率更高, 你也不得不承认.
握手言和吧 ....... I fule you.
A
Another_eYes
Unregistered / Unconfirmed
GUEST, unregistred user!
形成a--b的映射关系? 谈何容易(对integer也许可能), 如果是指针(或类)怎么
办?是字串呢? 浮点数呢? 写的那个映射函数就将你的效率拉下来啦.
不过我的确得承认有限个数的integer, 你的效率的确最高.
办?是字串呢? 浮点数呢? 写的那个映射函数就将你的效率拉下来啦.
不过我的确得承认有限个数的integer, 你的效率的确最高.
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
P.S. 我占用的内存不必你多多少
b,是一样的
我多了链表节点,o(2n)
你的递归占用堆栈空间(参数,调用记录) 最好情况o(c*logn)
b,是一样的
我多了链表节点,o(2n)
你的递归占用堆栈空间(参数,调用记录) 最好情况o(c*logn)
张
张国龙
Unregistered / Unconfirmed
GUEST, unregistred user!
好啦, 我是很佩服你的
还是你的方法实用.
年轻气盛, 忍不住为自己多说两句,
你一直泡在网上吗?
我觉得我现在跟吸毒差不多, 总是人不住来大富翁
反而对delphi 摸的少了.我学delphi 一个多月了
水平还是上不去..., 练习太少, 真希望能找个
delphi 的工作, 自己学, 唉 !, 总是不能深入!
你是这儿的首富, 还望多多指点.
还是你的方法实用.
年轻气盛, 忍不住为自己多说两句,
你一直泡在网上吗?
我觉得我现在跟吸毒差不多, 总是人不住来大富翁
反而对delphi 摸的少了.我学delphi 一个多月了
水平还是上不去..., 练习太少, 真希望能找个
delphi 的工作, 自己学, 唉 !, 总是不能深入!
你是这儿的首富, 还望多多指点.
Z
zlq
Unregistered / Unconfirmed
GUEST, unregistred user!
多人接受答案了。
Similar threads
- RickLee
- 局域网 / 通讯