PAT-BASIC1005——继续(3n+1)猜想

我的PAT-BASIC代码仓：https://github.com/617076674/PAT-BASIC

原题链接：https://pintia.cn/problem-sets/994805260223102976/problems/994805320306507776

题目描述：

知识点：集合

思路：用一个集合存储输入的每一个数字的过程数

时间复杂度和每个数字有关，不好计算。空间辅助度亦是如此。

C++代码：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> addToOverrideNums(int num, vector<int> overrideNums);
bool compareNum(int num1, int num2);

int main() {
	int count;
	cin >> count;

	vector<int> inputNums;
	vector<int> overrideNums;
	vector<int> result;
	
	for (int i = 0; i < count; i++) {
		int num;
		cin >> num;
		inputNums.push_back(num);
		overrideNums = addToOverrideNums(num, overrideNums);
	}

	for (int i = 0; i < inputNums.size(); i++) {
		if (std::find(overrideNums.begin(), overrideNums.end(), inputNums[i]) != overrideNums.end()) {
			continue;
		}
		result.push_back(inputNums[i]);
	}
	sort(result.begin(), result.end(), compareNum);
	for (int i = 0; i < result.size(); i++) {
		cout << result[i];
		if (i != result.size() - 1) {
			cout << " ";
		}
	}
}

vector<int> addToOverrideNums(int num, vector<int> overrideNums) {
	while (num > 1) {
		if (num % 2 == 0) {
			num /= 2;
		} else {
			num = (3 * num + 1) / 2;
		}
		if (num != 1) {
			overrideNums.push_back(num);
		}
	}
	return overrideNums;
}

bool compareNum(int num1, int num2) {
	if (num1 > num2) {
		return true;
	} else {
		return false;
	}
}

C++解题报告：

JAVA代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[] nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = scanner.nextInt();
        }
        ArrayList<Integer> result = new ArrayList<>();
        ArrayList<Integer> overridedNums = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            overridedNums.addAll(overridedNumbers(nums[i]));
        }
        for (int i = 0; i < count; i++) {
            if(overridedNums.contains(nums[i])){
                continue;
            }
            result.add(nums[i]);
        }
        Collections.sort(result);
        Collections.reverse(result);
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i));
            if(i != result.size() - 1){
                System.out.print(" ");
            }
        }
    }

    private static ArrayList<Integer> overridedNumbers(int num){
        ArrayList<Integer> arrayList = new ArrayList<>();
        while(num > 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                num = (3 * num + 1) / 2;
            }
            arrayList.add(num);
        }
        return arrayList;
    }
}

JAVA解题报告：