Cho một dãy gồm N số. Một số trong dãy gọi là số chính nếu số lần xuất hiện của số đó lớn hơn N / 2. Viết chương trình tìm số chính trong dãy.Input: SOCHINH.INP: dòng đầu tiên gồm số N (N < 10^6), N dòng tiếp theo mỗi dòng ghi 1 số trong dãy, |ai| < 10^9.Output: SOCHINH.OUT: gồm 1 số duy nhất là chỉ số của số chính tìm được, -1 nếu không tồn tại số như vậy.
Bài tập Pascal: Số chính
Ai giúp em với ạ. Cám ơn nhiều.
Sử dụng nguyên tắc nếu có 2 phần tử khác nhau trong dãy thì sự xuất hiện của nó sẽ cancel lẫn nhau (Moore Voting algorithm), bạn có thể làm bài này bằng 2 lần duyệt mảng.
[ah]
[/ah]
Bạn cũng có thể không cần lưu lại mảng cũng đc; khi đó chỉ cần đọc file 2 lần là xong.
[ah]
Mã:
function majorityElement : longint;
var i, index, count : longint;
begin
index := 1;
count := 1;
for i := 2 to n do
begin
if (a[i] = a[index]) then
inc(count)
else
dec(count);
if (count = 0) then
begin
index := i;
count := 1;
end;
end;
count := 0;
for i := 1 to n do
if (a[i] = a[index]) then
inc(count);
if (count > n div 2) then
exit(index);
exit(-1);
end;Bạn cũng có thể không cần lưu lại mảng cũng đc; khi đó chỉ cần đọc file 2 lần là xong.
Bài này đơn giản ý mà thuật toán của tui tối ưu nè 1 vòng for là ra { xem lại phần khai báo để tối ưu nhé tui làm tổng quát gần hết trường hợp thui }
Mã:
program so_chinh;
Const Fi = 'SOCHINH.INP';
Fo = 'SOCHINH.OUT';
Var F1 , F2 : Text;
N ,i,max,sc,x: longint;
A : Array[-1000010..1000010]of longint;
Begin
Assign(F1,Fi);
Reset(F1);
Assign(F2,Fo);
Rewrite(F2);
Readln(F1,N);
For i:=1 to N do
Begin
Read(F1,x);
A[x]:=A[x]+1;
if max<a[x] then
begin
max:=a[x];
sc:=x;
end;
end;
if max> (N div 2) then write(f2,sc)
else write(f2,-1);
close(F2);
End.Bạn xem lại giới hạn dữ liệu: 10^9 = 1 tỷ. Bạn cần 1 mảng 2 tỷ phần tử, mỗi phần tử là longint với 4 byte, tức là cần 8 tỷ byte = ??? GB RAM?
Độ phức tạp thuật toán của bạn là O
, cũng bằng với cách kia, nhưng bạn tiêu hao bộ nhớ quá lớn. Đấy là mình chưa tính tới phải tốn thời gian initialize mảng bằng 0 đấy. Mặc dù code ko có nhưng compiler nó vẫn phải chạy qua 2 tỷ phần tử để set từng ô giá trị 0.
PS: sc = i mới đúng vì in ra chỉ số, chứ ko phải số chính.
Độ phức tạp thuật toán của bạn là O
, cũng bằng với cách kia, nhưng bạn tiêu hao bộ nhớ quá lớn. Đấy là mình chưa tính tới phải tốn thời gian initialize mảng bằng 0 đấy. Mặc dù code ko có nhưng compiler nó vẫn phải chạy qua 2 tỷ phần tử để set từng ô giá trị 0.PS: sc = i mới đúng vì in ra chỉ số, chứ ko phải số chính.
Sửa lần cuối:
Chưa tới 8GB RAM (giga ~ tỷ). Thật ra nếu space (bộ nhớ) ko giới hạn thì đây là 1 cách hay. Ví dụ như trong sort, cứ việc dùng 1 mảng bao trùm range của dữ liệu thì độ phức tạp của thuật toán chỉ còn OTính sơ sơ thì 8 tỷ byte bằng 8000 GB RAM thì phải
, chứ ko còn O(n log n) nữa. Cách này gọi là bucket sort.Tuy nhiên, quan trọng là cách làm #4 không làm thay đổi độ phức tạp của thuật toán (vẫn là O
), bởi vậy sẽ ko đc làm trong thật tế. Ví dụ như mảng input chỉ mỗi 2 phần tử mà phải dùng gần 8GB RAM thì quá nhiều. Ng` ta chỉ trade memory for speed trong một giới hạn nào đó.
Sửa lần cuối:
Tớ còn nhiều thiếu sót mong mọi người giúp đỡ nhiều ạ!!Chưa tới 8GB RAM (giga ~ tỷ). Thật ra nếu space (bộ nhớ) ko giới hạn thì đây là 1 cách hay. Ví dụ như trong sort, cứ việc dùng 1 mảng bao trùm range của dữ liệu thì độ phức tạp của thuật toán chỉ còn O
Tuy nhiên, quan trọng là cách làm #4 không làm thay đổi độ phức tạp của thuật toán (vẫn là O
Thống kê
Bài viết được quan tâm nhiều
-
Lộ diện thiết kế OnePlus 13
- Tin Tức
