子数组合并,换位问题

lcy3125891

1。
   设a[0:n-1]是一个有n个元素的数组，k(0<=k<=n-1)是一个非负整数．试设计一个算法将子数组
a[0:k]与a[k+1:n-1]换位．要求算法在最坏情况下耗时O(n), 且只用到O(1)的辅助空间．

2。
   设子数组a[0:k]和a[k+1:n-1]已排好序（0<=k<=n-1).试设计一个合并这两个子数组为排好序的数组a[0:n-1]的算法．要求算法在最坏的情况下所用的计算时间为O(n), 且只用到O(1)的辅助空间．

请高手指点一下吧，说说思路，能有代码更好！

BenBear

第一个，可以 reverse 实现。先把 a[0:k] 和 a[k+1:n-1] 分别反转，再把整个 a[0:n-1] 反转。反转的算法可以是 O(n) 的时间和 O(1) 的辅助空间。

lcy3125891

谢谢

converse

第一题,不用二楼说的reverse的方法的话可以这么做:

1. 
   
2. #include <stdio.h>
   
3. 
   
4. void DisplayArray(int *pArray, int nLen)
   
5. {
   
6.         for (int i = 0; i < nLen; ++i)
   
7.         {
   
8.                 printf("array[%d] = %d\n", i, pArray[i]);
   
9.         }
   
10. }
    
11. 
    
12. void SwapSubArray(int *pArray1, int *pArray2, int n)
    
13. {
    
14.         int temp;
    
15.         for (int i = 0; i < n; ++i)
    
16.         {
    
17.                 temp = *(pArray1 + i);
    
18.                 *(pArray1 + i) = *(pArray2 + i);
    
19.                 *(pArray2 + i) = temp;
    
20.         }
    
21. }
    
22. 
    
23. void ChangeArray(int *pArray, int nLen, int k)
    
24. {
    
25.         if (NULL == pArray)
    
26.                 return;
    
27.         if (k < 0 || k > nLen - 1)
    
28.                 return;
    
29.        
    
30.         if (2 == nLen)
    
31.         {
    
32.                 SwapSubArray(pArray, pArray + 1, 1);
    
33.                 return;
    
34.         }
    
35. 
    
36.         int m, n, num;
    
37.         if (nLen - k - 1 > k + 1)                                                                // 如果后半部分的元素多
    
38.         {
    
39.                 m = nLen - k - 1 - k - 1;                                                        // m是两部分元素数量之差
    
40.                 SwapSubArray(pArray, pArray + k + 1 + m, k + 1);        // 交换两部分元素数目相同的部分
    
41.                 ChangeArray(pArray, nLen - k - 1, k);
    
42.         }
    
43.         else if (nLen - k - 1 < k + 1)                                                        // 如果前半部分的元素多
    
44.         {
    
45.                 m = k + 1 - nLen + k + 1;
    
46.                 SwapSubArray(pArray, pArray + k + 1, k + 1 - m);        // 交换两部分元素数目相同的部分
    
47.                 ChangeArray(pArray + nLen - k - 1, k + 1, m - 1);
    
48.         }
    
49.         else                                                                                                        // 前后两部分元素数量相同
    
50.         {
    
51.                 SwapSubArray(pArray, pArray + k + 1, k + 1);
    
52.         }
    
53. }
    
54. 
    
55. int main()
    
56. {
    
57.         int array[] = {0, 1, 2, 3, 4, 5, 6, 7};
    
58.         int nLen = sizeof(array) / sizeof(array[0]);
    
59.         DisplayArray(array, nLen);
    
60. 
    
61.         ChangeArray(array, nLen, 1);
    
62.         printf("after change:\n");
    
63.         DisplayArray(array, nLen);
    
64. 
    
65.         return 1;
    
66. }
    

复制代码

里面用到了递归,我不清楚是不是符合你的要求了.
具体的思想就是分别交换前后两部分数量相同的部分,然后再进行元素交换.

[ 本帖最后由 converse 于 2006-9-26 19:47 编辑 ]

converse

第二题很简单的了,看看代码就清楚了:

1. 
   
2. 
   
3. #include <stdio.h>
   
4. 
   
5. void DisplayArray(int *pArray, int nLen)
   
6. {
   
7.         for (int i = 0; i < nLen; ++i)
   
8.         {
   
9.                 printf("array[%d] = %d\n", i, pArray[i]);
   
10.         }
    
11. }
    
12. 
    
13. // pArray1和pArray2是已经排好序的数组,要求将它们按照顺序合并到pArray中
    
14. // 排序之后的数组不会有重复的元素
    
15. void MergeArray(int *pArray1, int nLen1, int *pArray2, int nLen2, int *pArray)
    
16. {
    
17.         int i, j, n;
    
18. 
    
19.         i = j = n = 0;
    
20.         while (i < nLen1 && j < nLen2)                        // 循环一直进行到拷贝完某一个数组的元素为止
    
21.         {
    
22.                 if (pArray1[i] < pArray2[j])                // 拷贝array1的元素
    
23.                 {
    
24.                         pArray[n++] = pArray1[i++];
    
25.                 }
    
26.                 else if (pArray1[i] > pArray2[j])        // 拷贝array2的元素
    
27.                 {
    
28.                         pArray[n++] = pArray2[j++];                       
    
29.                 }
    
30.                 else                                                                // 相等的元素拷贝
    
31.                 {
    
32.                         pArray[n++] = pArray2[j++];                       
    
33.                         ++i;
    
34.                 }
    
35.         }
    
36. 
    
37.         if (i == nLen1)                                                        // 如果array1已经被拷贝完毕就拷贝array2的元素
    
38.         {
    
39.                 while (j < nLen2)
    
40.                         pArray[n++] = pArray2[j++];
    
41.         }
    
42.         else                                                                        // 如果array2已经被拷贝完毕就拷贝array1的元素
    
43.         {
    
44.                 while (i < nLen1)
    
45.                         pArray[n++] = pArray1[i++];
    
46.         }
    
47. }
    
48. 
    
49. int main()
    
50. {       
    
51.         int array1[] = {1, 3, 5, 7};
    
52.         int array2[] = {2, 4, 6, 8};
    
53.         int array3[8];
    
54.         MergeArray(array1, 4, array2, 4, array3);
    
55.         printf("Merge Array:\n");
    
56.         DisplayArray(array3, 8);
    
57. 
    
58.         return 1;
    
59. }
    
60. 
    

复制代码

lcy3125891

非常谢谢converse ，不过你好像理解错第二题的意思了，题目是不能开辟新数组空间的。
刚才在CSDN上有人告诉我说第二题是不能实现的，除非用链表，看来是这样了。

converse

原帖由 lcy3125891 于 2006-9-26 21:21 发表
非常谢谢converse ，不过你好像理解错第二题的意思了，题目是不能开辟新数组空间的。
刚才在CSDN上有人告诉我说第二题是不能实现的，除非用链表，看来是这样了。

不开辟新的,如何保证两个是连在一起的?显然只能用链表了

lcy3125891

不好意思，这是我们的＜＜算法设计与分析＞＞里的一道题目，我也是刚知道无解的．

carleo21

第一题
基本思路是尽量将每个元素直接移到其应该在的位置，总的操作数为数组长度N，只需要用一个临时空间。例如
0 1 2 3 4 5 6 7 8
3 4 5 6 7 8 0 1 2
操作步骤为
tmp = a[0]; a[0] = a[3]; a[3] = a[6]; a[6] = tmp;
tmp = a[1]; a[1] = a[4]; a[4] = a[7]; a[7] = tmp;
....
关键是找出 a[ i ] = a[t], 在这里记数组长度为n，第一个子数组的长度为k，容易得出
t = ( i < n - k) ? (i + k) : ( i - n + k);
还有就是注意上面这种“循环”的情况，所以在代码中有 if ( j == t) 的条件判断。

#include <stdio.h>
#define N 9

void swaparray(int *, int, int);

int main(int argc, char **argv)
{
        int i;
        int a[N];
        for (i = 0; i < N; i++)
                a[i] = i;
       
        swaparray(a, N, 6);
        for (i = 0; i < N; i++)
                printf("%2d ",a[i]);
        putchar('\n');
        return 0;
}

/*
*@n Length of a
*@k Length of first subarray
*/
void swaparray(int *a, int n, int k)
{
        int i, j, t, c, tmp;
        i = j = c = 0;
       
        if ( a == NULL || k < 1 || k >= n || n < 1)
                return;
       
        while (c < n){
                i = j;
                tmp = a[i];
                while (1) {
                        t = (i < n - k) ? (i + k) : (i - n + k);
                        if ( j == t){
                                break;
                        } else {
                                a[i] = a[t];
                                i = t;
                                c++;
                        }
                }
                a[i] = tmp;
                c++;
                j++;
        }
       
}

converse

carleo21 (carleo)  的算法很好,学习了~~