length trong mảng - tin tuc the thao trong nuoc

Giới thiệu bài toán

Cho một mảng số nguyên nums, hãy trả về tổng của làm tròn xuống(nums[i] / nums[j]) cho tất cả các cặp chỉ số 0 <= i, j < nums.length trong mảng. Vì kết quả có thể rất lớn, hãy trả về giá trị đó theo modulo 10^9 + 7. Hàm làm tròn xuống() sẽ trả về phần nguyên của phép chia.

Ví dụ minh họa

Ví dụ 1:

Đầu vào: nums = [2,5,9]
Đầu ra: 10
Giải thích:
làm tròn xuống(2 / 5) = làm tròn xuống(2 / 9) = làm tròn xuống(5 / 9) = 0
làm tròn xuống(2 / 2) = làm tròn xuống(5 / 5) = làm tròn xuống(9 / 9) = 1
làm tròn xuống(5 / 2) = 2
làm tròn xuống(9 / 2) = 4
làm tròn xuống(9 / 5) = 1
Chúng ta tính toán phép làm tròn xuống của phép chia cho mỗi cặp chỉ số trong mảng và sau đó cộng chúng lại.

Ví dụ 2:

Đầu vào: nums = [7,7,7,7,7,7,7] tin tức the thao bóng đá
Đầu ra: 49

Điều kiện ràng buộc:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Phân tích ngắn gọn

Bài toán này xứng đáng là mức độ khó, nếu không nhờ vào lời giải của một bậc thầy trong khu vực thảo luận, chắc chắn mình đã phải suy nghĩ rất lâu. Có hai điểm chính cần lưu ý: đối với bất kỳ số nào trong mảng, ví dụ như k, cách đơn giản nhất là lặp qua tất cả các cặp số và thực hiện phép chia k, nhưng điều này sẽ gây ra hiệu suất thấp. Thay vào đó, ta nhận lịch bóng đá ngoại hạng anh thấy rằng:

• Đối với tất cả các số nhỏ hơn k, khi chia chúng cho k, kết quả làm tròn xuống luôn bằng 0, vì vậy không cần xét đến.
• Đối với tất cả các số lớn hơn hoặc bằng k, chúng ta có thể chia chúng thành các khoảng cụ thể như [k, 2k-1), [2k, 3k-1), [3k, 4k-1)... Trong mỗi khoảng này, kết quả làm tròn xuống của phép chia k sẽ giống nhau. Do đó, thay vì tính từng cặp riêng lẻ, chúng ta có thể tính tổng số lượng phần tử trong mỗi khoảng và nhân với kết quả tương ứng.

Tóm lại, để tính toán hiệu quả, ta chỉ cần biết có bao nhiêu số bằng k và có bao nhiêu số nằm trong mỗi khoảng liên quan đến k.

Mã nguồn

 1static final int MAXE5 = 100_000;
 2static final int MODULUSE9 = 1_000_000_000 + 7;
 3
 4public int sumOfFlooredPairs(int[] nums) {
 5    int[] counts = new int[MAXE5+1];
 6    for (int num : nums) {
 7        counts[num]++;
 8    }
 9    
10    // Tính toán số lần xuất [Live Casino](/post/7aee9b0987602201.html)  hiện của từng phần tử trong mảng
11    for (int i = 1; i <= MAXE5; i++) {
12        counts[i] += counts[i - 1];
13    }
14    
15    long total = 0;
16    for (int i = 1; i <= MAXE5; i++) {
17        long sum = 0;
18        if (counts[i] == counts[i-1]) {
19            continue;
20        }
21        
22        for (int j = 1; i*j <= MAXE5; j++) {
23            int min = i * j - 1;
24            int upper = i * (j + 1) - 1;
25            sum += (counts[Math.min(upper, MAXE5)] - counts[min]) * (long)j;
26        }
27        
28        total = (total + (sum % MODULUSE9) * (counts[i] - counts[i-1])) % MODULUSE9;
29    }
30    
31    return (int)total;
32}