当前位置:编程学习 > C/C++ >>

两个数之和等于第三个数

这是一个很好的算法题,解法类似于快速排序的整理方法。同时,更为值得注意的是这道题是 人人网2014校园招聘的笔试题,下面首先对题目进行描述:
      给出一个有序数组,另外给出第三个数,问是否能在数组中找到两个数,这两个数之和等于第三个数。
      我们首先看到第一句话,这个数组是有序的,所以,我们可以定义两个指针,一个指向数组的第一个元素,另一个指向应该指向的位置(这个需要看具体的实现和数组给定的值),首先计算两个位置的和是否等于给定的第三个数,如果等于则算法结束,如果大于,则尾指针向头指针方向移动,如果小于,则头指针向尾指针方向移动,当头指针大于等于尾指针时算法结束,没有找到这样的两个数。
      它看起来就好像下面这张图一样:
 
      下面给出具体的实现:
 
#include <stdio.h>  
  
int judge(int *a, int len, int k, int *num1, int *num2);  
  
int main(int argc, char **argv)  
{  
    int test_array[] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};  
    int result = -1;  
    int num1, num2;  
    result = judge(test_array, sizeof(test_array) / sizeof(int), 12, &num1, &num2);  
    if(result == 0)  
    {  
        printf("%d\t%d\n", num1, num2);  
    }  
    else if(result == -1)  
    {  
        printf("can't find");  
    }  
    else  
    {  
        printf("error");  
    }  
}  
  
int judge(int *a, int len, int k, int *num1, int *num2)  
{  
    int *low = NULL;  
    int *high = NULL;  
    int i = 0;  
    int result = -1;  
    if(a == NULL || len < 2)  
    {  
        return result;  
    }  
    if(a[0] >= k)  
    {  
        return result;  
    }  
    while(a[i] <= k && i < len)  
    {  
        i++;  
    }  
    low = a;  
    high = a + i - 1;  
    while(low  < high)  
    {  
        *num1 = *low;  
        *num2 = *high;  
        if((*low + *high) == k)  
        {  
            result = 0;  
            break;  
        }  
        else if((*low + *high) > k)  
        {  
            high--;  
        }  
        else if((*low + *high) < k)  
        {  
            low++;  
        }  
    }  
    return result;  
}  

 


补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,