数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在C++中查找N个整数数组中的非空子集，使得子集元素之和能被N整除
假设我们有一个包含n个数字的数组；我们必须找到一个非空子集，使得子集元素的和可以被n整除。因此，我们必须输出任何这样的子集及其大小以及原始数组中元素的索引（如果存在）。
因此，如果输入类似于[3, 2, 7, 1, 9]，则输出将为[2]，[1 2]。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个map my_map
- add := 0
- 对于初始化 i := 0，当 i < N 时，更新（i增加1），执行：
- add := (add + arr[i]) mod N
- 如果add等于0，则：
- 打印 i + 1
- 对于初始化 j := 0，当 j <= i 时，更新（j增加1），执行：
- 打印 j + 1
- 返回
- 如果add在my_map中，则：
- 打印 (i - my_map[add])
- 对于初始化 j := my_map[add] + 1，当 j <= i 时，更新（j增加1），执行：
- 打印 j + 1
- 返回
- 否则
- my_map[add] := i
示例 (C++)
让我们看看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
void subset_find(int arr[], int N) {
unordered_map<int, int> my_map;
int add = 0;
for (int i = 0; i < N; i++) {
add = (add + arr[i]) % N;
if (add == 0) {
cout << i + 1 << endl;
for (int j = 0; j <= i; j++)
cout << j + 1 << " ";
return;
}
if (my_map.find(add) != my_map.end()) {
cout << (i - my_map[add]) << endl;
for (int j = my_map[add] + 1; j <= i; j++)
cout << j + 1 << " ";
return;
}
else
my_map[add] = i;
}
}
int main() {
int arr[] = {3, 2, 7, 1, 9};
int N = sizeof(arr) / sizeof(arr[0]);
subset_find(arr, N);
}输入
{3, 2, 7, 1, 9}输出
2 1 2
更新于：2020年8月28日
296 次浏览
广告