เราได้รับเมทริกซ์ขนาด NXN เป้าหมายคือการหาจำนวนคู่ของดัชนีที่ถูกต้องทั้งหมด (i,j) โดยที่องค์ประกอบรวมของคอลัมน์ j มีค่ามากกว่าผลรวมขององค์ประกอบของแถว i
เราจะทำสิ่งนี้โดยข้ามเมทริกซ์และคำนวณผลรวมขององค์ประกอบของแต่ละแถวและคอลัมน์
จัดเก็บผลรวมขององค์ประกอบของแต่ละองค์ประกอบใน rowsum[N] และผลรวมขององค์ประกอบของแต่ละคอลัมน์ใน colsum[N]
ตอนนี้สร้างคู่ของ rowsum[i] และ colsum[j] และตรวจสอบว่า colsum[j]>rowsum[i] หากการเพิ่มขึ้นจริงนับสำหรับคู่ดังกล่าว
มาทำความเข้าใจกับตัวอย่างกัน
Input-: matrix= {
{ 1,2,0,1},
{ 3,3,0,2},
{ 1,3,0,2},
{ 3,0,0,2}
}; ผลผลิต − จำนวนคู่ที่ถูกต้อง − 9
คำอธิบาย −
Rowsum[0]= 1+2+0+1=5 Colsum[0]= 1+3+1+3=8 Rowsum[1]=3+3+0+2=8 Colsum[1]= 2+3+3+0=8 Rowsum[2]= 1+3+0+2=6 Colsum[2]= 0+0+0+0=0 Rowsum[3]=3+0+0+2=5 Colsum[3]= 1+2+2+2=7 Pairs of (i,j) such that rowsum[i] < colsum[j]. (0,0), (0,1), (0,3), (2,0), (2,1), (2,3), (3,0) (3,1), (3,3)
ป้อนข้อมูล −
Arr[]= { {1,1,1}, {1,1,1}, {1,1,1} } N=3 ผลผลิต − จำนวนคู่ที่ถูกต้อง − 0
คำอธิบาย −
Rowsum[0]= 1+1+1=3 Colsum[0]= 1+1+1=3 Rowsum[1]= 1+1+1=3 Colsum[1]= 1+1+1=3 Rowsum[2]= 1+1+1=3 Colsum[2]= 1+1+1=3 No pairs possible where rowsum[i]<colsum[j]
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
เราใช้อาร์เรย์จำนวนเต็ม Arr[] ที่เริ่มต้นด้วยตัวเลขสุ่ม
-
ใช้ตัวแปร n ซึ่งเก็บความยาวของ Arr[].
-
ฟังก์ชัน countPairs(int arr[], int n) รับอาร์เรย์ ความยาวเป็นอินพุตและส่งกลับคู่ที่ถูกต้องและตรงตามเงื่อนไขที่ต้องการ
-
เราใช้สองแถว rowsum[n] และ colsum[n].
-
ข้ามเมทริกซ์และเพิ่ม arr[i][j] ไปที่ rowsum[i] และ colsum[j] เพื่อคำนวณผลรวมของแถว i และคอลัมน์ j
-
ตอนนี้สำรวจอาร์เรย์ colsum[] และ rowsum[] โดยใช้สองลูป
-
หากมี colsum[j]>rowsum[i]. จำนวนที่เพิ่มขึ้น
-
คืนค่าการนับเป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr[][3], int n){
// Count of pairs
int count = 0;
int rowsum[n]={0};
int colsum[n]={0};
int i,j;
for (i = 0; i < n; i++){
for (j = 0; j < n; j++){
rowsum[i]+=arr[i][j];
colsum[j]+=arr[i][j];
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++)
if(colsum[j]>rowsum[i])
{ count++; }
}
return count;
}
int main(){
int Arr[][3] = { {1,3,5},{2,4,6},{3,5,7} };
int side=3;
cout <<endl<<"Count of number of pairs : "<< countPairs(Arr, side);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of number of pairs : 4
