每日编程中遇到任何疑问、意见、建议请公众号留言或加入每日编程群聊739635399
在一个递增有序的数组中，有数值相同的元素存在，程序的功能是去掉数值相同的元素，使数组中不再有重复的元素。例如（7,10,10,21,30,42,42,42,51）变成（7,10,21,30,42,51）
算法要求：尽量优化算法的时间复杂度与空间复杂度。
输入格式：
数组元素的个数
数组元素（以空格隔开）
输出格式：
新数组输入样例：
9
7 10 10 21 30 42 42 42 51
输出样例：
7 10 21 30 42 51
解决方法：
（1）算法的基本思想：
确定该数组为递增有序。
那么只是需要比较相邻两个元素的值即可。在这里我们可以换一种思考方式，可以采用直接插入排序的思想，若要插入的一个元素在数组中存在，则不插入。
另一种思考方式是设计一个辅助数组（较常用），设计两个指针i，j分别指向原数组和辅助数组，比较原数组中的值和辅助数组中的值，若相同，则i++，否则将数据插入到辅助数组中，两个指针同时后移，直到遍历完原数组。
两种排序方式比较：采用直接排序的思想，其时间复杂度为O（n^2），空间复杂度为O（1）。
采用增加一个辅助数组的方法，时间复杂度为O（n），空间复杂度为O（n）。
（2）代码实现：
#include
using namespace std;
//按照第一种方式-直接插入排序的方式来去除同样的元素
void deleteSame1(int a[], int n)
{
int i, j;
for (i = 0, j = 1; j < n; j++)
if (a[i] != a[j])
a[++i] = a[j];
for (int k = 0; k < (i + 1); k++)
cout << a[k] << " ";
cout << endl;
}
//按照方式二来去除数组中的相同的元素，需要借助额外的n个空间
void deleteSame2(int a[], int n)
{
int *b = new int[n];
int i = 0, k = 0;
//数组b中存储的数据为a中按从小到大均不相同的数据
b[0] = a[0];
while (i < n)
{
if (a[i] == b[k])
{
i++;
continue;
}
else
{
b[++k] = a[i++];
}
}
for (int j = 0; j <= k; j++)
cout << b[j] << " ";
cout << endl;
}
int main()
{
int a[100] = {0}; //假设数组中元素的最大值为100
int n = 0;
cin >> n;
getchar();
//为n个元素赋值
for (int i = 0; i < n; i++)
cin >> a[i];
deleteSame1(a, n);
//deleteSame2(a,n);
system("pause");
return 0;
}
从数据结构中树的定义可知，除根节点外，树中的每个节点都有唯一的一个双亲结点。根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各结点。树中的结点除保存本身结点的信息外，还要保存其双亲结点在数组中的位置（即在数组中的下标。双亲的信息为-1则表示该结点为根结点），树的这种表示方法称为双亲表示法。
树中的每个结点的数据类型定义如下：
typedef struct {
char data; //结点数据域
int parent; //结点双亲在数组中的位置
} PTNode；
树的数据类型定义如下：
#define MAX_TREE_SIZE 100
typedef struct {
PTNodenodes[MAX_TREE_SIZE]; //存储树中所有的结点
int n; //树中的结点数，n不超过100
} PTree;
则下图所示的树中，按照双亲表示法存储结构，存储为图b所示的形式（n为10）。
已知一棵树以存储以上形式，请编写函数GetLeavesCount，计算叶子结点数目。
GetLeavesCount的函数原型为：int GetLeavesCount（PTree T）
其中，形参T中保存了树中的结点数目以及图b所示的结点数组，函数返回叶子结点的数目。
比如：对图b的树调用函数GetLeavesCount（T），返回结果为6
输入的第一个数n表示树中的结点数，此后有n行输入，每行表示一个节点的信息，第一个信息为结点的数据，第二个信息为结点的双亲结点在数组中的位置。
如输入：
10
a -1
b 0
c 0
d 0
e 1
f 1
g 1
h 2
i 3
则创建图b所对应的树。
对此树调用函数GetLeavesCount（T）,返回结果为6
如输入：
8
a -1
b 0
e 1
h 2
c 0
d 0
f 5
g 5
对此树调用函数GetLeavesCount（T）,返回结果为4
输入格式：
结点个数
结点信息
输出格式：
叶子结点的个数输入样例：
10
a -1
b 0
c 0
d 0
e 1
f 1
g 1
h 2
i 3
h 3
输出样例：
6
