Question

求大神给出完整c++源代码，在线等！！！！

问题描述：一个整形数组int a[100] 保存1-100 现在随机将其中两个数改为0， 找出这两个数，要求时间和空间复杂度尽量小

Answer 1

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>

using namespace std;

const int sum = 5050;
const int sum2 = 338350;

void find(int *a)
{
	int m = sum, n = sum2;
	for(int i = 0; i < 100; ++ i)
	{
		m -= a[i];
		n -= a[i] * a[i];
	}
	int x = (sqrt((2 * n - m * m) * 1.0) + m) / 2;
	cout << x << " " << m - x << endl;
}

int main()
{
	int a[100];
	for(int i = 0; i < 100; ++ i)
	{
		a[i] = i + 1;
	}
	srand((unsigned int)time(NULL));
	a[rand() % 50] = 0;
	a[rand() % 50 + 50] = 0;
	cout << "Display after changes" << endl;
	for(int i = 0; i < 100; ++ i)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	find(a);
	return 0;
}

追问

有没有步骤分析？时间和空间复杂度是怎么理解的？

追答

两个未知数a,b,我知道a+b=m,a^2+b^2=n,求出a,b不是套用公式？结果应该很显然。
对于这个程序，你只需要看find函数
时间复杂度是O(n)，我只是扫描了下数组再多几个单独操作
空间复杂度是O(1),毕竟数组是题目的要求，我开辟的辅助空间就是几个常量
如果你第二个问题问的是定义，我建议你好好看书，连这些都不懂最好别先搞算法