解题思路
这是一个无倍数数查找问题。关键点如下:
- 给定
个互不相同的正整数
- 需要找出所有的无倍数数(一个数是无倍数数,当且仅当其他数都不是它的倍数)
- 按升序输出所有无倍数数
解题思路:
- 首先存储所有正整数
- 对于每个数,检查其他数是否是它的倍数
- 如果没有其他数是它的倍数,则它是无倍数数
- 最后对结果进行排序并输出
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
// 存储输入的数
vector<int> nums;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 0) nums.push_back(x);
}
// 找出无倍数数
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
bool isNoMultiple = true;
for (int j = 0; j < nums.size(); j++) {
if (i != j && (nums[j] % nums[i] == 0)) {
isNoMultiple = false;
break;
}
}
if (isNoMultiple) {
result.push_back(nums[i]);
}
}
// 排序并输出
sort(result.begin(), result.end());
for (int i = 0; i < result.size(); i++) {
cout << result[i];
if (i < result.size() - 1) cout << " ";
}
cout << endl;
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 存储输入的数
ArrayList<Integer> nums = new ArrayList<>();
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
if (x > 0) nums.add(x);
}
// 找出无倍数数
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.size(); i++) {
boolean isNoMultiple = true;
for (int j = 0; j < nums.size(); j++) {
if (i != j && nums.get(j) % nums.get(i) == 0) {
isNoMultiple = false;
break;
}
}
if (isNoMultiple) {
result.add(nums.get(i));
}
}
// 排序并输出
Collections.sort(result);
for (int i = 0; i < result.size(); i++) {
System.out.print(result.get(i));
if (i < result.size() - 1) System.out.print(" ");
}
System.out.println();
}
}
n = int(input())
nums = [int(x) for x in input().split() if int(x) > 0]
# 找出无倍数数
result = []
for i in range(len(nums)):
is_no_multiple = True
for j in range(len(nums)):
if i != j and nums[j] % nums[i] == 0:
is_no_multiple = False
break
if is_no_multiple:
result.append(nums[i])
# 排序并输出
result.sort()
print(" ".join(map(str, result)))
算法及复杂度
- 算法:暴力枚举
- 时间复杂度:
- 需要对每个数检查其他所有数
- 空间复杂度:
- 需要存储输入数组和结果数组