Thắc mắc bug trong bài code đếm số lần lặp

#1

Chào các bác ạ, em mới học lập trình C++ và được giao cho bài tập đếm số lần lặp trong mảng này nhưng em gặp lỗi khiến chương trình chạy không được như ý, em đã suy nghĩ nhưng vẫn không tìm được lỗi sai ạ. Mong các bác chỉ giúp em với, em cảm ơn nhiều ạ.

image
image491×650 16.5 KB 

#include <iostream>
using namespace std;
int main() {
int n,i;
cin >> n ;
int arr[n+1];
int lap=1;
for (i=0;i<n;i++) {
    cin >> arr[i];
}
for (i=0;i<n;i++) {
for (i=1;i<n;i++) {
    if ( arr[0]==arr[i])
    lap++;
} cout << arr[i] << " " << lap << endl;
}
}
#2

bạn có tự chạy chương trình và nhập thử input như đề bài chưa?

1 Like
#3

e đã thử tự chạy trên compiler khác nhưng kqua vẫn giống như trên ảnh em chụp ấy ạ

#4

mình hỏi lúc bạn ngồi lập trình và chạy thử trên máy bạn, kết quả có đúng hay không?
trên máy bạn chạy ra đúng mà khi chấm lại sai? hay là như nào

1 Like
#5

bạn giải giải thích code của bạn, tối nhất là chi tiết từng dòng, bạn muốn làm gì khi viết dòng code đó

1 Like
#6

chương trình vẫn chạy nhưng kết quả ra sai như trên ảnh em có đính kèm ở trên ấy ạ.

#7

à em biết về mặt logic e sai ở đâu r ạ. Em mới chỉ cho lặp hàm for để kiểm tra số lần lặp của phần tử thứ nhất thôi ạ chứ các phần tử từ thứ 2 trở đi em chưa đếm số lần lặp. Liệu anh có thể gợi ý hoặc hướng dẫn em đc k ạ

#8 
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e6;

int a[N];

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n;i++){
		cin >> a[i];
	}
	sort (a,a+6);
	int cnt = 1;
	for(int i = 1; i < n;i++){
		if(a[i] == a[i-1]) ++cnt;
		else{
			cout << a[i-1] << " " << cnt << endl;
			cnt = 1;
		}
	}
	cout <<  a[n-1] << " " << cnt << endl;
	
}

em có tham khảo được trên mạng cách đếm số lần lặp này và đã hiểu nhưng nếu như khi cout ra kết quả em muốn giữ nguyên thứ tự các phần tử trong mảng như trước khi dùng hàm sort thì có cách nào không ạ ?

#9

Đây sẽ là các mình làm. Đương nhiên nó có thể được cải thiện một cách nào đó nhưng cách tiếp cận sẽ như nhau.

#include <iostream>

int main() {
    int n;
    std::cin >> n;
    int a[n], d[n];
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        d[i] = 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (d[j] == 0) {
                continue;
            }
            if (a[i] == a[j]) {
                d[i]++;
                d[j] = 0;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (d[i] != 0) {
            std::cout << a[i] << " " << d[i] << "\n";
        }
    }
    return 0;
}

Chỉ là một vòng lặp so sánh thông thường thôi. Độ phức tạp sẽ là O(n^2-n)

Mình có thêm mảng d[n] là để lưu trữ số lần lặp của từng phần tử ở vị trí trong mảng. Ví dụ trong test 1 thì 4 ở vị trí 0 của mảng a thì d[0] sẽ là 2 vì nó đếm phần tử 4 được lặp 2 lần. Mảng d[n] còn có thêm mục đích nữa là kiểm tra xem phần tử đã được so sánh chưa, nếu rồi thì bộ đếm nó là 0 và khi in ra nếu số lần lặp của nó là 0 thì mình hiểu là nó đã được so sánh rồi và bỏ qua nó.

2 Likes
#10

O(n^2 - n) chính là O(n^2) thôi bạn :crazy_face:

C++ không có trò này đâu nên bạn bỏ thói quen viết như thế này đi nhé.

2 Likes
#11

Khi d[i] bằng 0 tức là a[i] đã đếm rồi, vậy thì không cần chạy vòng lặp biến j nữa.

   for (int i=0; i<n; ++i) {
      if (!d[i]) continue;
      for (int j=i+1; j<n; ++j) {
         if (a[i] == a[j]) {
            ++d[i];
            d[j] = 0;
         }
      }
   }

Worst-case là mảng đôi một khác nhau, chắc phải dùng std::unordered_map thật.

2 Likes
#12

Việc gán d[j] tức là a[j] đã được đếm cùng với a[i] nên không cần phải lặp nó ở lần sau nữa. Nếu không đánh dấu nó thì ví dụ trong test 1 ngoài 4 2 ra nó sẽ in thêm 4 1 mặc dù số 4 ở cuối đã được đếm cùng số 4 ở đầu rồi.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?