计算大小为n的矩阵中k的频率，其中matrix(i, j) = i + j
原文： https://www.geeksforgeeks.org/count-frequency-k-matrix-size-n-matrixi-j-ij/
给定大小为n * n的矩阵。 计算该矩阵中给定元素k的频率。 这里的基本索引是 1。
例子：
Input : n = 4, k = 7
Output : 2
Explanation
The matrix will be
2 3 4 5
3 4 5 6
4 5 6 7
5 6 7 8
in the given matrix where M(i, j) = i+j,
frequency of 7 is 2
Input : n = 5, k = 4
Output : 3
Explanation
The matrix will be
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
6 7 8 9 10
Explanation
In the given matrix where M(i, j) = i+j,
frequency of 4 is 3
第一种方法：
-
构造大小为
n * n的矩阵。 -
用
M(i, j) = i + j填充值。（回想这里的基本索引为 1）。 -
遍历矩阵并计算给定元素的频率。
这种方法效率不高，因为如果矩阵大小很大，将导致超过时间限制。时间复杂度将为O(n ^ 2)。
有效方法：
在此方法中，我们避免创建大小为n * n的矩阵。
例如，如果n = 10，则矩阵为：
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
4 5 6 7 8 9 10 11 12 13
5 6 7 8 9 10 11 12 13 14
6 7 8 9 10 11 12 13 14 15
7 8 9 10 11 12 13 14 15 16
8 9 10 11 12 13 14 15 16 17
9 10 11 12 13 14 15 16 17 18
10 11 12 13 14 15 16 17 18 19
11 12 13 14 15 16 17 18 19 20
现在，请注意第二对角线中的值如何相同，我们还可以发现计数增加的模式，例如 1、2、3、4，在这里我们可以看到，如果(n + 1) >= k，则k的频率为k-1，否则频率将为2 * n + 1-k。
CPP
// CPP program to find the frequency of k
// in matrix where m(i, j)=i+j
#include <bits/stdc++.h>
using namespace std;
int find(int n, int k)
{
if (n + 1 >= k)
return (k - 1);
else
return (2 * n + 1 - k);
}
// Driver Code
int main()
{
int n = 4, k = 7;
int freq = find(n, k);
if (freq < 0)
cout << " element not exist \n ";
else
cout << " Frequency of " << k
<< " is " << freq << "\n";
return 0;
}
Java
// Java program to find the
// frequency of k in matrix
// in matrix where m(i, j)=i+j
import java.util.*;
import java.lang.*;
public class GfG{
public static int find(int n, int k)
{
if (n + 1 >= k)
return (k - 1);
else
return (2 * n + 1 - k);
}
// Driver function
public static void main(String argc[])
{
int n = 4, k = 7;
int freq = find(n, k);
if (freq < 0)
System.out.print(" element"
+ " not exist \n ");
else
System.out.print(" Frequency"
+ " of " + k + " is " +
freq + "\n");
}
}
// This code is contributed by Sagar Shukla
Python3
# Python program to find
# the frequency of k
# in matrix where
# m(i, j)=i+j
import math
def find( n, k):
if (n + 1 >= k):
return (k - 1)
else:
return (2 * n + 1 - k)
# Driver Code
n = 4
k = 7
freq = find(n, k)
if (freq < 0):
print ( " element not exist")
else:
print(" Frequency of " , k ," is " , freq )
# This code is contributed
# by Gitanjali.
C#
// C# program to find the
// frequency of k in matrix
// in matrix where m(i, j)=i+j
using System;
public class GfG{
public static int find(int n, int k)
{
if (n + 1 >= k)
return (k - 1);
else
return (2 * n + 1 - k);
}
// Driver function
public static void Main()
{
int n = 4, k = 7;
int freq = find(n, k);
if (freq < 0)
Console.WriteLine(" element"
+ " not exist ");
else
Console.WriteLine(" Frequency"
+ " of " + k + " is " +
freq );
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to find the frequency of k
// in matrix where m(i, j)=i+j
function find($n, $k)
{
if ($n + 1 >= $k)
return ($k - 1);
else
return (2 * $n + 1 - $k);
}
// Driver Code
$n = 4;
$k = 7;
$freq = find($n, $k);
if ($freq < 0)
echo " element not exist \n ";
else
echo " Frequency of " , $k
, " is " , $freq , "\n";
// This code is contributed by anuj_67\.
?>
Output:
Frequency of 7 is 2
版权属于：月萌API www.moonapi.com，转载请注明出处
