判断数组中是否存在两个数之和为指定值

判断数组中是否存在两个数之和为指定值

题目是CLRS 2.3-7。原题如下:

Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x,determines whether or not there exist two elements in S whose sum is exactly x.

初看这个题目,就大约想到用排序来解决。我大概的思路是先排序,然后再用二分查找法去寻找。

看了看CLRS的答案,给出的方法跟我思路不同,他的想法是,添加一个数组,其值为原输入数组中值与x的差,删除掉两个数组中相同的数,然后合并排序那两个数组,如果合并排序后数组中相邻的两个数相同,则说明原数组中有sum为x的元素。

觉得答案给出的方法也比较有意思,于是试着实现了一下。过程中还真遇到了点问题,下次要吸取教训。

问题是这样的,要删除原数组中相同的元素,我用的如下的方法:

// assume array, length is defined.
int i = 0;
for(; i < length - 1; i++){
    if(array[i] == array[i+1]){
        int tmp = i;
        while(tmp < length - 1){
            array[tmp] = array[tmp + 1];
            tmp++;
        }
    }
}

看出问题在哪儿了吗?在遇到这样{-26 -23 -22 -19 -18 1 2 2 2 14}的输入时,结果就会不对了,经过这样的代码处理后,数组输出为{-26 -23 -22 -19 -18 1 2 2 14}。在考虑修改这段代码时,进一步发现,其实不用输出到原有数组中的,因为最后要把数组的元素拷贝到合并数组中,所以可以用合并数组来记录,于是有了最终的代码。

#include 

void Merge(int array[], int start, int mid, int end){
//    printf("Merge start = %d, mid = %d, end = %d\n", start, mid, end);
//    int kk;
//    printf("BEFORE*****\n");
//    for(kk = start; kk <= end; kk++){
//        printf("%d ", array[kk]);
//    }
//    printf("\n");
    if(end > start){
        int tmpArray[end - start + 1];
        int i = 0;
        int s1 = start;
        int s2 = mid;
        while(s1 <= mid - 1 && s2 <= end){
//            printf("s1=%d, s2=%d, array[s1]=%d, array[s2]=%d\n",s1,s2,array[s1],array[s2]);
            if(array[s1] <= array[s2]){
                tmpArray[i++] = array[s1];
                s1++;
            }else if(array[s1] > array[s2]){
                tmpArray[i++] = array[s2];
                s2++;
            }
        }
        for(; i < end - start + 1; i++){
            if(s1 > mid - 1){
                tmpArray[i] = array[s2++];
            }else if (s2 > end){
                tmpArray[i] = array[s1++];
            }
        }
        for(i = start; i <= end; i++){
            array[i] = tmpArray[i-start];
        }
//        printf("AFTER*****\n");
//        for(kk = start; kk <= end; kk++){
//            printf("%d ", array[kk]);
//        }
//        printf("\n");
    }
}

void MergeSort(int array[], int start, int end){
    if(end > start){
        int mid = (start + end) / 2;
//        printf("\nmid = %d\n", mid);
        MergeSort(array, start, mid);
        MergeSort(array, mid + 1, end);
        Merge(array, start, mid + 1, end);
    }
}

/**
 * Input: array, the sum of two element.
 * This function returns whether there exist sum of two elements
 * in a array equal to input sum.
 *
 */
int ReturnPulsValue(int array[], int arrayLength, int sum){
    // 1. sort source array
    MergeSort(array, 0, arrayLength - 1);
    int tmpArray[arrayLength];
    int i;
    // 2. genereate tmpArray which all element in it equals to
    // sum - array[i]
    for(i = 0; i < arrayLength; i++){
        tmpArray[i] = sum - array[i];
    }
    // 3. sort tmpArray
    MergeSort(tmpArray, 0, arrayLength - 1);
    printf("\nsort first array result\n");
    for(i = 0; i < arrayLength; i++){
        printf("%d ", array[i]);
    }
    printf("\nsort second array result\n");
    for(i = 0; i < arrayLength; i++){
        printf("%d ", tmpArray[i]);
    }
    // 4. kick off same element in the array.
    int targetMergeArray[arrayLength * 2];
    int targetMergeArrayIdx = 0;
    for(i = 0; i < arrayLength - 1; i++){
        if(array[i] != array[i+1]){
            targetMergeArray[targetMergeArrayIdx++] = array[i];
        }
    }
    targetMergeArray[targetMergeArrayIdx++] = array[arrayLength - 1];
    int mid = targetMergeArrayIdx;
    for(i = 0; i < arrayLength - 1; i++){
        if(tmpArray[i] != tmpArray[i+1]){
            targetMergeArray[targetMergeArrayIdx++] = tmpArray[i];
        }
    }
    targetMergeArray[targetMergeArrayIdx] = tmpArray[arrayLength - 1];
    
    printf("\ntargetMergeArray array before merge\n");
    for(i = 0; i <= targetMergeArrayIdx; i++){
        printf("%d ", targetMergeArray[i]);
    }
    // 5. Merege array & tmpArray        
    Merge(targetMergeArray, 0, mid, targetMergeArrayIdx);
    printf("\ntargetMergeArray array after merge\n");
    for(i = 0; i <= targetMergeArrayIdx; i++){
        printf("%d ", targetMergeArray[i]);
    }
    // 6. Find out whether there are same vaule in merged array.
    for(i = 0; i < targetMergeArrayIdx; i++){
        if(targetMergeArray[i] == targetMergeArray[i + 1]){
            return 1;
        }
    }
    
    return 0;
}

int main(int argc, char** argv){
    int length = 10;
    int array[] = {40,0,12,13,37,12,36,33,12,32};
    int findOutSum = 14;
    int i = 0;
    srand(time(NULL));
    printf("Find out sum = %d in array, array is \n", findOutSum);
    for(; i < length; i++){
        //int randNumber = rand() % 41;
        //array[i] = randNumber;
        printf("%d ", array[i]);
    }
    printf("\n");
    int rtn = ReturnPulsValue(array, length, findOutSum);
    printf("\nreturn  = %d \n", rtn);
    
    return 0;
}

注:这段代码在遇到{17 21 12 40 3 18 25 15 7 39}这样的数组,如果要找和为14时,会出错。避免的办法就不在这里写了。

Leave a Reply

Your email address will not be published. Required fields are marked *