本文主要是介绍另一种检查数组中是否有两元素之和等于给定数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
//给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个数其和刚好为x#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>int merge(int * objary,unsigned int index_start,unsigned int index_middle,unsigned int index_end)
{int n1 = index_middle - index_start + 1;int n2 = index_end - index_middle;int * leftary = (int *)malloc(n1 * sizeof(int));int * rightary = (int *)malloc(n2 * sizeof(int));int i,j,k = index_start;for(i = 0;i < n1; ++i){leftary[i] = objary[k];k ++;}for(j = 0;j < n2; ++j){rightary[j] = objary[k];k ++;}i = 0;j = 0;for(k = index_start; k <= index_end; ++ k){if(leftary[i] <= rightary[j]){objary[k] = leftary[i];++ i;if(i == n1)break;}else{objary[k] = rightary[j];++ j;if(j == n2)break;}}++ k;if(i == n1){for(; j < n2; ++ j){objary[k] = rightary[j];++ k;}}else if(j == n2){for(; i < n1; ++ i){objary[k] = leftary[i];++ k;}}free(leftary);free(rightary);leftary = NULL;rightary = NULL;
}
void merge_sort(int * objary,unsigned int index_start,unsigned int index_end)
{unsigned int index_middle;if(index_start < index_end){index_middle = (index_start + index_end) / 2;merge_sort(objary,index_start,index_middle);merge_sort(objary,index_middle + 1,index_end);merge(objary,index_start,index_middle,index_end);}
}
bool is_number_in_array(int array[],int number,int length){int start = 0;int end = length - 1;int half = (start + end) / 2;while(end > start){if(number > array[half]){printf("start:%d,half:%d,end:%d\n",start,half,end);printf("%d,%d\n",array[half],number);start = half ;half = (start + end) / 2;}else if(number < array[half]){printf("start:%d,half:%d,end:%d\n",start,half,end);printf("%d,%d\n",array[half],number);end = half ;half = (start + end) / 2;}else{return true;}}return false;
}bool IS_num_sum_of_two_elements(int array[],int sum,int length){merge_sort(array,0,length - 1);for(int i = 0; i < length; i ++){int j = length - 1;int sum_value = array[i] + array[j];if(sum < sum_value){j -= 1;}else if(sum > sum_value){i += 1;}elsereturn true;}return false;
}int main() {int array[] = {3,41,52,26,38,57,9,49};int length = sizeof(array)/ sizeof(array[0]);if(IS_num_sum_of_two_elements(array,200,length - 1))printf("true\n");elseprintf("false\n");return 0;
}
这篇关于另一种检查数组中是否有两元素之和等于给定数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!