Đang tải…
Đang tải…
Tìm giá trị chiếm hơn một nửa mảng chỉ với một bộ đếm và không cần bộ nhớ phụ — các giá trị khác nhau tự triệt tiêu.
Bộ đếm về 0, nghĩa là mọi thứ trước điểm này đã triệt tiêu vừa khít. Nhận a[0] = 3 làm ứng viên mới với một phiếu.
1int majority(int[] a) {2 int candidate = 0, count = 0;3 for (int x : a) {4 if (count == 0) { candidate = x; count = 1; }5 else if (x == candidate) count++;6 else count--; // hai giá trị khác nhau triệt tiêu — đó là toàn bộ mẹo7 }8 int seen = 0;9 for (int x : a) if (x == candidate) seen++; // luôn kiểm chứng: vẫn có ứng viên dù không có đa số10 return seen > a.length / 2 ? candidate : -1;11}