算法和数据结构试题

---------------------------------------------------------------------------

1. 二叉排序树和哈希表那个查找效率高。

普遍而言，哈希表更快。但要看具体情况。
二叉排序树的查找复杂度一般为 O(logn)。但如果退化为链表，则复杂度为 O(n)。
哈希表的查找速度要看哈希函数，一般为 O(1)。但如果哈希表容量太小，或者哈希函数很容易导致冲突，将大大降低查找速度。极端情况下，哈希表的容量为 1，或者所有元素都被映射到哈希表中的同一项，此时哈希表也退化为链表，复杂度也为 O(n)。

---------------------------------------------------------------------------

2. 在一个已经排好序的数组里面把重复的值删除掉。

思路：用两个指针，前面的指针如果发现当前项和下一项值不同的话，就把下一项的值拷贝到后面指针的下一项中，两个指针同时后移；如果发现当前项和下一项值相同的话，前指针就向下移动，后指针不动。

#include <stdio.h>

int deduplicate(int arr[], int n)
{
int count;
int * tmp = arr;
int * end = arr + n - 1;

if (!arr)
{
return 0;
}

count = 0;
while (tmp != end)
{
if (*tmp != *(tmp + 1))
{
*arr++ = *tmp;
++count;
}
++tmp;
}

/*
* 如果 n=1，则 while 循环一次都没有执行，这里是复制数组中唯一的一个元素；
* 如果最后两个元素相等，则这里是复制最后相等的那个元素
* (在 while 循环中没有被复制)；
* 如果最后两个元素不等，则这里是复制最后那个不等的元素。
*/
*arr = *end;
++count;

return count;
}

int main(int argc, char * argv[])
{
int i;
int arr1[] = {1};
int arr2[] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};
int arr3[] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6};
int len;

/* 测试只有一个元素的情况。 */
len = deduplicate(arr1, sizeof(arr1) / sizeof(arr1[0]));
printf("Length after deduplicate: %d\n", len);
for (i = 0; i < len; ++i)
{
printf("%d ", arr1[i]);
}
printf("\n");

/* 测试最后两个元素相同的情况。 */
len = deduplicate(arr2, sizeof(arr2) / sizeof(arr2[0]));
printf("Length after deduplicate: %d\n", len);
for (i = 0; i < len; ++i)
{
printf("%d ", arr2[i]);
}
printf("\n");

/* 测试最后两个元素不同的情况。 */
len = deduplicate(arr3, sizeof(arr3) / sizeof(arr3[0]));
printf("Length after deduplicate: %d\n", len);
for (i = 0; i < len; ++i)
{
printf("%d ", arr3[i]);
}
printf("\n");

return 0;
}


参考：http://www.it.com.cn/f/edu/0611/9/347299_5.htm

---------------------------------------------------------------------------

3. 在一个循环有序的数组里查找特定值。(循环有序就是指数组里的各项都是有序的，但是最小值不一定是数组的第 0 项，而可能是其中任意一项，然后逐项递增，到数组尾的时候再回到第 0 项)

在这样的数组中查找就不能直接使用二分法了。可以使用一个二分法的变形，除了判断中心值之外，还要判断两端的值，以此确定循环开始点在中点的哪一边，并判断所查找的值是否在循环起始点的哪边，并采用不同的处理方式。

#include <stdio.h>

int mysearch(int arr[], int s, int e, int value)
{
int m = (s + e) / 2;
for (; s < e; m = (s + e) / 2)
{
if (arr[m] == value)
{
return m;
}

/*
* s m e
* 1 2 3
*/
if (arr[s] <= arr[m] && arr[m] <= arr[e])
{
if (value < arr[m])
{
e = m - 1;
}
else
{
s = m + 1;
}
}
/*
* s m e
* 2 3 1
*/
else if (arr[s] <= arr[m] && arr[m] >= arr[e])
{
if (value < arr[m] && value >= arr[s])
{
e = m - 1;
}
else
{
s = m + 1;
}
}
/*
* s m e
* 3 1 2
*/
else
{
if (value > arr[m] && value <= arr[e])
{
s = m + 1;
}
else
{
e = m - 1;
}
}
}
if (arr[s] == value)
{
return s;
}

return -1;
}

int main(int argc, char * argv[])
{
int i;
int arr[] = {70, 80, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int len = sizeof(arr) / sizeof(arr[0]);

for (i = 0; i < len; ++i)
{
printf("%d\n", mysearch(arr, 0, len - 1, arr[i]));
}

return 0;
}

---------------------------------------------------------------------------

4. 设 S1, S2, ..., Sk 是 k 个集合，每个集合均由 n 个整数组成。设计一个程序将所有的和 { x1+x2+...+xk | xi 属于 Si, i=1,...,k } 从小到大排序。

下面是一个思路，虽然不正确，但可以参考一下。先在这放着，等想出来了再更新。
(不正确的原因：请考虑 S1 = {0, 4, 5}, S2 = {1, 3, 6} 的情况)

把所有和按从小到大的顺序找出。

对每个集合先排序，定义 k 个指针 p1, p2, ..., pk。它们初始指向 k 个集合的最小元素。下面用 Sipi 表示 pi 在 Si 中指向的元素, pi+1 表示 pi 的下一个元素，(1<=i<=k)

最小元素是 A：A = S1p1 + S2p2 + ... + Skpk
1. 在 p1+1, p2+1, ..., pk+1 中找出使得 pi+1 - pi (1<=i<=k) 最小的元素，假设是 pj+1。
2. 更新 pj 的值：pj=pj+1
则此时的新和：S1p1 + S2p2 + ... + Sjpj + ... + Skpk 是比 A 大的最小元素

重复步骤 1 和 2 直到所有指针都指向集合的最后一个元素 (此时找到的必然是所有和中的最大值)。


参考：http://topic.csdn.net/t/20051004/13/4307070.html

---------------------------------------------------------------------------

5. 去掉整型数组中的重复数字。要求结果保留原数组的顺序。

思路一：
将原数组的下标值存在一个辅助数组中 (也就是说辅助数组为 {0, 1, 2, 3, ...})。然后根据下标指向的值对辅助数组排序，对排序后的辅助数组去重 (也是根据下标指向的值)。然后再按下标本身的值对去重后的辅助数组排序。之后顺次读出剩下的各下标指向的值即可。
例如：原数组为 {1, 2, 0, 2, -1, 999, 3, 999, 88}，则辅助数组为 {0, 1, 2, 3, 4, 5, 6, 7, 8}，对辅助数组按下标指向的值排序的结果为 {4, 2, 0, 1, 3, 6, 8, 5, 7}，对辅助数组按下标指向的值去重的结果为 {4, 2, 0, 1, 6, 8, 5}，对辅助数组按下标本身排序的结果为 {0, 1, 2, 4, 5, 6, 8}，最后得到的结果为 {1, 2， 0， -1， 999， 3， 88}。
复杂度分析：主要的时间在两次排序，所以时间复杂度为 O(NlogN)。

思路二：
利用平衡二叉树。一开始建立一棵空平衡二叉树。然后顺次读取源数组，每读出一个整数，就在该平衡二叉树中查找该整数，若找到，则读取下一个整数，若找不到，则输出该整数，并将该整数插入到平衡二叉树中。
复杂度分析：平衡二叉树的插入和查找都是 O(logN) 的，所以总的时间复杂度为 O(NlogN)。
STL 中的 set 就是利用平衡二叉树实现的。下面是利用 set 的一个实现：

#include <iostream>
#include <set>

using namespace std;

int main(int argc, char * argv[])
{
set<int> p;
int array[] = {1, 2, 0, 2, -1, 999, 3, 999, 88};
int len = sizeof(array) / sizeof(array[0]);
int i;
cout << array[0];
p.insert(array[0]);
for (i = 1; i < len; ++i)
{
if (p.find(array[i]) == p.end())
{
p.insert(array[i]);
cout << " ," << array[i];
}
}
cout << endl;
p.clear();

return 0;
}


参考：http://community.csdn.net/Expert/TopicView3.asp?id=5603029

---------------------------------------------------------------------------