[PAT 乙级] 1005 继续(3n+1)猜想 (25 分)——(Hash散列)2021-08-26

我的代码

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(int a,int b){
    return a>b;
}
int main() {
    int num;
    map<int,int> mp;
    cin >> num;
    for (int i = 0; i < num; i++) {
        int n;
        cin>>n;
        if(mp[n]!=1) mp[n]=0;
        while (n != 1) {
            if (n % 2 != 0) {
                n = 3 * n + 1;
                n /= 2;
                mp[n]=1;
            }
            else {
                n = n / 2;
                mp[n]=1;
            }
        }
    }
    vector<int> v;
    for(auto it=mp.begin();it!=mp.end();it++){
        if(mp[it->first]==0) v.push_back(it->first);
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<v.size();i++){
        if(i==0) cout<<v[i];
        else cout<<" "<<v[i];
    }
    return 0;
}
           

柳神代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[10000];
bool cmp(int a, int b) { return a > b; }
int main() {
	int k, n, flag = 0;
	cin >> k;
	vector<int> v(k);
	for (int i = 0; i < k; i++) {
		cin >> n;
		v[i] = n;
		while (n != 1) {
			if (n % 2 != 0) n = 3 * n + 1;
			n = n / 2;
			if (arr[n] == 1) break;
			arr[n] = 1;
		}
	}
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < v.size(); i++) {
		if (arr[v[i]] == 0) {
			if (flag == 1) cout << " ";
			cout << v[i];
			flag = 1;
		}
	}
	return 0;
}