原文:
给定一个整数数组和两个数字 k 和 m。从数组中打印 k 个数字，这样任意两对之间的差可以被 m 整除。如果没有 k 个数字，则打印-1。 例:
input: arr[] = {1, 8, 4}
k = 2
m = 3
output: 1 4
explanation: difference between
1 and 4 is divisible by 3.
input: arr[] = {1, 8, 4}
k = 3
m = 3
output: -1
explanation: there are only two numbers
whose difference is divisible by m, but
k is three here which is not possible,
hence we print -1.
一种天真的方法是对每个元素进行迭代，并与所有其他元素进行检查，如果差可被 m 整除的数字的计数大于或等于 k，那么我们通过再次迭代来打印那些 k 个数字。但是这不够高效，因为它运行两个嵌套循环。 时间复杂度:o(n * n) 辅助空间:o(1) 一种高效的方法是应用一种数学方法，在这里我们知道(x-y) % m 是否等于 x % m–y % m。所以如果我们可以存储所有在除以 m 时留下相同余数的数， 并且如果留下相同余数的数的计数大于 k 或者等于 k，那么我们就有了我们的答案，就像所有留下相同余数的数一样。 以下是上述方法的实施
c
// cpp program to find a list of k elements from
// an array such that difference between all of
// them is divisible by m.
#include
using namespace std;
// function to generate k numbers whose difference
// is divisible by m
void print_result(int a[], int n, int k, int m)
{
// using an adjacency list like representation
// to store numbers that lead to same
// remainder.
vector v[m];
for (int i = 0; i < n; i ) {
// stores the modulus when divided
// by m
int rem = a[i] % m;
v[rem].push_back(a[i]);
// if we found k elements which
// have same remainder.
if (v[rem].size() == k)
{
for (int j = 0; j < k; j )
cout << v[rem][j] << " ";
return;
}
}
// if we could not find k elements
cout << "-1";
}
// driver program to test the above function
int main()
{
int a[] = { 1, 8, 4 };
int n = sizeof(a) / sizeof(a[0]);
print_result(a, n, 2, 3);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to find a list of k elements from
// an array such that difference between all of
// them is divisible by m.
import java.util.*;
class gfg
{
// function to generate k numbers whose difference
// is divisible by m
static void print_result(int a[], int n,
int k, int m)
{
// using an adjacency list like representation
// to store numbers that lead to same
// remainder.
vector> v = new vector>(m);
for(int i = 0; i < m; i )
v.add(new vector());
for (int i = 0; i < n; i )
{
// stores the modulus when divided
// by m
int rem = a[i] % m;
v.get(rem).add(a[i]);
// if we found k elements which
// have same remainder.
if (v.get(rem).size() == k)
{
for (int j = 0; j < k; j )
system.out.print(v.get(rem).get(j) " ");
return;
}
}
// if we could not find k elements
system.out.print("-1");
}
// driver code
public static void main(string[] args)
{
int a[] = { 1, 8, 4 };
int n = a.length;
print_result(a, n, 2, 3);
}
}
// this code is contributed by 29ajaykumar
python 3
# python3 program to find a list of k elements from
# an array such that difference between all of
# them is divisible by m.
# function to generate k numbers whose difference
# is divisible by m
def print_result(a, n, k, m):
# using an adjacency list like representation
# to store numbers that lead to same
# remainder.
v = [[] for i in range(m)]
for i in range(0, n):
# stores the modulus when divided
# by m
rem = a[i] % m
v[rem].append(a[i])
# if we found k elements which
# have same remainder.
if(len(v[rem]) == k):
for j in range(0, k):
print(v[rem][j], end=" ")
return
# if we could not find k elements
print(-1)
# driver program to test the above function
if __name__=='__main__':
a = [1, 8, 4]
n = len(a)
print_result(a, n, 2, 3)
# this code is contributed by
# sanjit_prasad
c
// c# program to find a list of k elements from
// an array such that difference between all of
// them is divisible by m.
using system;
using system.collections.generic;
class gfg
{
// function to generate k numbers whose difference
// is divisible by m
static void print_result(int []a, int n,
int k, int m)
{
// using an adjacency list like representation
// to store numbers that lead to same
// remainder.
list> v = new list>(m);
for(int i = 0; i < m; i )
v.add(new list());
for (int i = 0; i < n; i )
{
// stores the modulus when divided
// by m
int rem = a[i] % m;
v[rem].add(a[i]);
// if we found k elements which
// have same remainder.
if (v[rem].count == k)
{
for (int j = 0; j < k; j )
console.write(v[rem][j] " ");
return;
}
}
// if we could not find k elements
console.write("-1");
}
// driver code
public static void main(string[] args)
{
int []a = { 1, 8, 4 };
int n = a.length;
print_result(a, n, 2, 3);
}
}
// this code is contributed by princiraj1992
服务器端编程语言（professional hypertext preprocessor 的缩写）
java 描述语言
输出:
1 4
时间复杂度:o(n) t3】辅助空间: o(m) 本文由供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
