问题描述:
有一个整数的数组a[N], 对于其中的元素a[i],如果其前面a[0]~a[i-1]中, 如果有且仅有一个元素比它大, 我们称之为独二元素。
设计一个函数, 输入一个数组a[N],找出其中所有的独二元素, 并输出出来;
如果没有这种元素, 什么也不干;
要求时间复杂度是O(n).
比如,输入数组: [10,9,9,8,11,10,12,11] 里面的独二元素: 第2个位置的9 第3个位置的9 第6个位置的10, 最后的11。
那么输出就是[9,9,10,11]。
代码如下:
int *seconds(int a[], int n, int *retSize) {
if (n >= 2) {
int *r = (int*)malloc(n * sizeof(*r));
int f = INT_MIN, s = INT_MIN, j = 0;
if (a[0] != a[1]) {
f = a[0] > a[1] ? a[0] : a[1];
s = a[0] + a[1] - f;
r[j++] = s;
} else {
f = a[0];
}
for (int i = 2; i < n; i++) {
if (a[i] < f && a[i] >= s) {
r[j++] = a[i];
}
if (a[i] > f) {
s = f;
f = a[i];
} else if (a[i] > s) {
s = a[i];
}
}
int *ret = (int*)malloc(j * sizeof(*ret));
for (int i = 0; i < j; i++) { ret[i] = r[i]; }
free(r);
if (retSize != NULL) { *retSize = j; }
return ret;
} else {
if (retSize != NULL) { *retSize = 0; }
return NULL;
}
}
思路:
用两个变量f(first), s(second)分别保存当前元素之前的所有元素中的最大和次大元素,然后对当前元素判断:
1)大于f且小于等于s则把当前元素加入结果集;
2)若当前元素大于f则更新f及s(刚刚代码忘了这一步同时更新s,后面有新一版代码);否则(即当前元素小于等于f),若当前元素大于s则更新s。
备注:最开始因为不知道一共多少个答案故malloc了一个和原输入数组同样大小的数组(其实最多就n-1个元素,即当输入数组第一个为最大的元素,其后跟着的子数组所有元素都小于第一个元素并且呈升序排列的时候,比如4, 1, 2, 3)。
网友评论