题目分析

  1. 题目给出我们一个int型整数输入
  2. 我们要返回将这个数字倒着读的新整数，并且不允许重复数字出现

方法一：转换成字符串

  • 实现思路

    • 我们以字符串方式来处理输入的整数

    • 由于需要倒序输出，所以我们遍历字符串的时候采用倒序访问的方式

    • 最终结果我们放在变量res中

    • 当倒序拿到每一个字符时，我们判断是否其已经出现在res中

      • 如果出现了则跳过
      • 如果未出现则将其添在尾处

    • 最终返回res即可

#include <iostream>

using namespace std;

int main() {
    string s;
    cin >> s;
    string res;
    for(int i = s.size() - 1; i >= 0; i--) {        // 倒序遍历输入字符串
        if(res.find(s[i]) == s.npos) {              // 在输出串中寻找当前字符
            res += s[i];
        }
    }
    cout << res;
    return 0;
}

复杂度分析

  • 时间复杂度：O(1)O(1)，外层遍历给定字符串，内层做find操作寻找是否有相同字符，因此代价为len2len^2，但是len的大小由于数据范围限定，因此也是在常量级别范围内
  • 空间复杂度：O(1)O(1)，借助了字符串的空间，和数据长度有关，但是由于n的范围在[1,108][1,10^8]，因此字符串长度也是常量大小

方法二：数学计算+标记数组

  • 实现思路
    • 我们对给定的数字n进行个位数字的获取，然后除以10来更新n的值
    • 对于每一个划出来的个位数字值来判断是否出现过，如果出现过则跳过本轮循环，如果未出现过则标记该数字已出现，并添加到res末尾
    • 最后输出res即可

alt

#include <iostream>

using namespace std;

int main() {
    int visited[10] = {0};			// 开辟10大小的空间专门记录是否出现过
    int n;
    int res = 0;
    cin >> n;
    while(n) {
        int digit = n % 10;			// 循环拿到个位数字
        if(!visited[digit]) {		// 如果没有出现过
            res *= 10;				// 则结果数据先乘10，再添加到末尾
            res += digit;
        }
        visited[digit] = 1;			// 标记该数字出现过
        n /= 10;					// 迭代n值
    }
    cout << res;
    return 0;
}

复杂度分析

  • 时间复杂度：O(1)O(1)，长度值由于数据范围的限制因此只能在[1,108][1,10^8]数据范围内，因此获得的len是个常量值大小，循环代价有限
  • 空间复杂度：O(1)O(1)，使用常量级别的空间大小记录出现次数