编写程序，对于无符号整数数组a。判断其中是否存在重复的元素（若有两个元素是相同的，输出1，否则输出0）。一个一个的去数组中找虽然是一种方法，但时间复杂性达到o(n 2 )，你能否将时间复杂性控制在o(n)。

题目描述：编写程序，对于无符号整数数组a。判断其中是否存在重复的元素（若有两个元素是相同的，则输出1，否则输出0）。一种一种的去数组中找然是一种方法，但时间复杂度达到O(n^2)，你能否将时间复杂度控制在O(n)。

解答：可以利用哈希表来实现时间复杂度为O(n)的算法，具体步骤如下：

1. 建立一个哈希表，用来存储数组中出现过的数。
2. 遍历数组a，对于每个元素a[i]，查找哈希表中是否存在该元素，如果存在，说明a[i]是重复元素，则输出1；如果不存在，则将a[i]插入哈希表，继续遍历数组。
3. 如果遍历完整个数组都没有找到重复元素，则输出0。

由于哈希查找的时间复杂度为O(1)，因此整个算法的时间复杂度为O(n)。

相关问题

假设无符号类型占16位，编写一个程序，从键盘输入两个值，将一个数的高八位做为结果的高八位，另一个数的高八位作为结果的低八位，输出结果的值

好的，您的问题是如何编写一个程序，从键盘输入两个值，将一个数的高八位做为结果的高八位，另一个数的高八位作为结果的低八位，输出结果的值。

以下是一个示例代码：

#include<stdio.h>

int main(){
    unsigned int a, b;

    printf("请输入两个16位无符号整数：\n");
    scanf("%hu%hu", &a, &b);

    // 取出输入的两个数的高8位，并把它们组合成一个新的16位数
    unsigned short result = (a >> 8) | (b & 0xFF00);

    printf("结果为：%hu\n", result);

    return 0;
}

这个程序先从键盘输入两个无符号整数，然后使用位运算符将一个数的高8位作为结果的高8位，另一个数的高8位作为结果的低8位，最后输出结果。

请注意，程序中使用了无符号整数类型unsigned int，它通常占32位，而不是16位，所以程序中使用了scanf函数的格式化字符串%hu来指定读入的两个数都是16位无符号整数。

C++的无符号整数类型表示范围有限,能表示的十进制无符号整数不超过 20位。编写程序,实现超过 20 位的无符号整数的加法和乘法运算。 要求程序读入文本文件 input. txt,计算其中的表达式的运算结果,并将结果输出到

一个文本文件 output.txt 中。

首先，我们可以使用 C++ 的字符串类 string 来实现超过 20 位的无符号整数。对于加法和乘法运算，我们可以借鉴手算加法和乘法的方法，从低位到高位逐位相加或相乘，并将进位或进位后的结果存储在一个数组中。

下面是一个简单的实现代码，仅供参考：

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> BigInt;

// 将字符串转换为 BigInt
BigInt strToBigInt(const string& s) {
    BigInt res;
    for (int i = s.length() - 1; i >= 0; i--) {
        res.push_back(s[i] - '0');
    }
    return res;
}

// 将 BigInt 转换为字符串
string bigIntToStr(const BigInt& num) {
    string res;
    for (int i = num.size() - 1; i >= 0; i--) {
        res += to_string(num[i]);
    }
    return res;
}

// 两个 BigInt 相加
BigInt addBigInt(const BigInt& a, const BigInt& b) {
    BigInt res;
    int carry = 0;
    int len = max(a.size(), b.size());
    for (int i = 0; i < len; i++) {
        int sum = carry;
        if (i < a.size()) sum += a[i];
        if (i < b.size()) sum += b[i];
        res.push_back(sum % 10);
        carry = sum / 10;
    }
    if (carry > 0) res.push_back(carry);
    return res;
}

// 两个 BigInt 相乘
BigInt mulBigInt(const BigInt& a, const BigInt& b) {
    BigInt res(a.size() + b.size(), 0);
    for (int i = 0; i < a.size(); i++) {
        int carry = 0;
        for (int j = 0; j < b.size(); j++) {
            int sum = a[i] * b[j] + carry + res[i+j];
            res[i+j] = sum % 10;
            carry = sum / 10;
        }
        if (carry > 0) res[i+b.size()] += carry;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

int main() {
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    string line;
    while (getline(fin, line)) {
        if (line.empty()) continue;
        // 解析表达式，支持多个数的加法和乘法运算
        vector<BigInt> nums;
        vector<char> ops;
        int start = 0;
        for (int i = 0; i <= line.length(); i++) {
            if (i == line.length() || line[i] == '+' || line[i] == '*') {
                string numStr = line.substr(start, i - start);
                nums.push_back(strToBigInt(numStr));
                if (i < line.length()) ops.push_back(line[i]);
                start = i + 1;
            }
        }
        // 计算结果
        BigInt res = nums[0];
        for (int i = 0; i < ops.size(); i++) {
            if (ops[i] == '+') {
                res = addBigInt(res, nums[i+1]);
            } else if (ops[i] == '*') {
                res = mulBigInt(res, nums[i+1]);
            }
        }
        fout << bigIntToStr(res) << endl;
    }
    fin.close();
    fout.close();
    return 0;
}

这个程序可以读取文本文件 input.txt 中的表达式，支持多个数的加法和乘法运算，计算结果后输出到文本文件 output.txt 中。注意，这个程序实现的加法和乘法运算时间复杂度较高，可能无法处理非常大的数字，需要根据具体情况进行优化。