조건에 맞는 두 수를 빠르게 찾기(두 수의 합은 주어진 값이다)
프로그램은 아래와 같습니다. 이 문제를 빌려서 MergeSort를 연습해 봅시다.
#include <stdio.h>
#include <boost/scoped_ptr.hpp>
void FindTargetSum(int array[], int begin, int end, int target_value) {
int min = begin;
int max = end;
int sum;
while (min < max) {
sum = array[min] + array[max];
if (sum > target_value) {
max--;
} else if (sum < target_value) {
min++;
} else {
printf("%d %d
", array[min], array[max]);
FindTargetSum(array, min - 1, max - 1, target_value);
break;
}
}
}
template<typename T>
void Merge(T array[], int begin, int middle, int end) {
int length1 = middle - begin + 1;
int length2 = end - middle;
boost::scoped_ptr<T> first_array_buffer(new T[length1]);
T* first = first_array_buffer.get();
boost::scoped_ptr<T> second_array_buffer(new T[length2]);
T* second = second_array_buffer.get();
for (int i = 0; i < length1; ++i) {
first[i] = array[begin + i];
}
for (int i = 0; i < length2; ++i) {
second[i] = array[middle + 1 + i];
}
int pos1 = 0;
int pos2 = 0;
int pos = begin;
while (pos1 < length1 || pos2 < length2) {
if (pos1 < length1 && pos2 < length2) {
if (first[pos1] < second[pos2]) {
array[pos++] = first[pos1++];
} else {
array[pos++] = second[pos2++];
}
} else if (pos1 < length1) {
array[pos++] = first[pos1++];
} else {
array[pos++] = second[pos2++];
}
}
}
template<typename T>
void MergeSort(T array[], int begin, int end) {
if (begin < end) {
int middle = (begin + end ) / 2;
// int middle1 = begin + (end - begin + 1) / 2;
// printf("--middle:%d, middle1:%d
", middle, middle1);
MergeSort(array, begin, middle);
MergeSort(array, middle + 1, end);
Merge(array, begin, middle, end);
}
}
template<typename T>
void Merge1(T array[], int begin, int middle, int end) {
int length1 = middle - 1 - begin + 1;
int length2 = end - middle + 1;
boost::scoped_ptr<T> first_buffer(new T[length1]);
T* first = first_buffer.get();
boost::scoped_ptr<T> second_buffer(new T[length2]);
T* second = second_buffer.get();
for (int i = 0; i < length1; ++i) {
first[i] = array[begin + i];
}
for (int i = 0; i < length2; ++i) {
second[i] = array[middle + i];
}
int pos = begin;
int pos1 = 0;
int pos2 = 0;
while (pos1 < length1 || pos2 < length2) {
if (pos1 < length1 && pos2 < length2) {
if(first[pos1] < second[pos2]) {
array[pos++] = first[pos1++];
} else {
array[pos++] = second[pos2++];
}
} else if (pos1 < length1) {
array[pos++] = first[pos1++];
} else {
array[pos++] = second[pos2++];
}
}
}
template<typename T>
void MergeSort1(T array[], int begin, int end) {
if (begin < end) {
int middle = begin + (end - begin + 1) / 2;
MergeSort1(array, begin, middle - 1);
MergeSort1(array, middle, end);
Merge1(array, begin, middle, end);
}
}
int main(int argc, char** argv) {
int array[] = {1, 5, 4, 7, 8 ,10};
size_t array_size = sizeof(array) / sizeof(int);
MergeSort1(array, 0, array_size - 1);
for (int i = 0; i < array_size; ++i) {
printf("%d ", array[i]);
}
printf("
");
FindTargetSum(array, 0, array_size - 1, 15);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Node.js에서 Base64 데이터를 이미지로 변환최근에 브라우저에서 이미지를 base64 형식으로 반환하는 프로젝트에 참여했고 이미지를 디스크에 써야 합니다. base64 , 버퍼, 바이너리 및 실제 이미지가 어떻게 작동하는지에 대한 자세한 설명을 얻을 수 있는지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.