本文共 1029 字,大约阅读时间需要 3 分钟。
转自:
11. 找到单向链表中间那个元素,如果有两个则取前面一个。
#include <stddef.h> struct listtype { int data; struct listtype * next; }; typedef struct listtype * list; /* Find the middle element of the singly linked list sll. */ list find_middle(list sll) { list slow = sll; list fast = sll; if (NULL == fast) { return NULL; } while (1) { if (NULL == fast->next || NULL == fast->next->next) { return slow; } slow = slow->next; fast = fast->next->next; /* Prevent that there is a loop in the linked list. */ if (fast == slow) { return NULL; } } } --------------------------------------------------------------------------- 12. 长度为 N 的整数数组,找出其中任意(N-1)个乘积最大的那一组,只能用乘法,不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析,不要求写程序。 令这 N 个数的乘积为 P, 1) 如果 P<0,则剔除其中最大的负整数即可; 2) 如果 P=0, 2.1) 若这 N 个数中有且仅有一个为“0”。若其他数之积为正,则剔除“0”;否则剔除任意一个非零数; 2.2) 若这 N 个数中至少有两个为“0”,则随便剔除一个数均可; 3) 如果 P>0,如果有正数,则剔除其中最小的正整数即可;否则,剔除最小的负整数。 时间复杂度:遍历数组,获得正整数个数 cp,负整数个数 cn,0 的个数 cz,需要 O(N) 时间;找被剔除的数最坏情况下需要 O(N) 时间。输出结果需要 O(N) 时间。因此,时间复杂度为 O(N)。 空间复杂度:数组存储需要 O(N) 空间,cp, cn, cz 和被剔除的数的下标各需要 O(1) 空间。因此,空间复杂度为 O(N)。 转载地址:http://qpeti.baihongyu.com/