cuốn sách gpt4 ai đã làm

Sự xuất hiện giống hệt nhau của hai số trong mảng con (liên tiếp)

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 05:33:39 28 4
mua khóa gpt4 Nike

Cho một dãy số nguyên, tìm tổng số các dãy con liên tiếp có cùng số x và y.Ví dụ: mảng [1,2,1] với x=1 và y=2 ans = 2 đại diện cho hai mảng con [1,2] và [2,1] của nó.Kiểm tra từng dãy con liên tiếp là O(n^2), điều này quá kém hiệu quả. Có ý tưởng nào để cải tiến không?

Đây là mã tôi đã viết

int get_total(int* a,int x,int y,int n){
kết quả int=0;
for(int i=0;i<>
int x_c=0,y_c=0;
for(int j=i;j<>
if(a[j]==x){
x_c++;
}
if(a[j]==y){
y_c++;
}
nếu(x_c==y_c){
kết quả++;
}
}
}
return result;
}

int chính(){
int n,q;
cin >>n >>q;
int a[n];
for(int i=0;i<>
cin >>a[i];
}
trong khi(q--){
int x,y;
cin >>x >>y;
cout <<>
}
}

Nó chạy trong n^2 cho mỗi truy vấn. Kích thước mảng tối đa là 8*10^3 và số lượng truy vấn tối đa là 10^5

câu trả lời hay nhất

Tạo một mảng phụ trợx_y_diff, Thiết yếu:

#(times_x_appeared_thus_far) - #(times_y_appeared_thus_far)

có thể được tính như sau:

x_y_diffs[0] = 0
x_y_diffs[i] = x_y_diffs[i-1] + 1 nếu mảng[i-1] == x
x_y_diffs[i-1] - 1 nếu mảng[i-1] == y
x_y_diffs[i-1] nếu không

Dễ dàng thấy rằng nó có thể được tính theo thời gian tuyến tính.

Bây giờ, hãy quan sát rằng dãy con "tốt" (i,j) là x_y_diffs[i+1] == x_y_diffs[j+1] bắt đầu và kết thúc.

Vì vậy, bạn có thể chỉ cần lặp lại mảng và duy trì biểu đồ đếm số lần mỗi giá trị xuất hiện.

std::map biểu đồ;
số int = 0;
cho (int x : x_y_diffs) {
đếm += biểu đồ [x];
biểu đồ[x] = biểu đồ[x] + 1;
}

Điều này đòi hỏi O(nlogn) thời gian để tính toán (mỗi lần chèn/tra cứu bản đồ là O(đăng nhập)) và có thể được cải thiện thành TRÊN) tình hình trung bình từ std::bản đồ chuyển sang std::unordred_map.

Do đó, tổng thuật toán TRÊN) hoặc O(nlogn) thời gian (dựa trên lựa chọn bản đồ) - và TRÊN) thêm không gian.

Demo trên ideone

Về c++ - Sự xuất hiện giống hệt nhau (liên tiếp) của hai số trong một mảng con, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/45205529/

28 4 0
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress