資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告