oral_quiz->#KLeastNumbers#

#include <stdio.h>
#include <exception>
#include <vector>
#include <set>

void PrintArrayFromI2J(int* data, int index1, int index2) {
	for(int i=index1; i<=index2; ++i) {
		printf("%d ", data[i]);
	}
	printf("
");
}

void Swap(int* p1, int* p2) {
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

int Partition(int* data, int length, int start, int end) {
	if(data == NULL || length <= 0 || start < 0 || end >= length)
		throw std::exception();

	int index = (start + end) >> 1;
	Swap(&data[index], &data[end]);

	int small = start - 1;
	for(index = start; index < end; ++index) {
		if(data[index] < data[end]) {
			++small;
			Swap(&data[small], &data[index]);
		}
	}

	++small;
	Swap(&data[small], &data[end]);

	return small;
}

bool g_bInputInvalid = false;

bool CheckInvalidArray(int* numbers, int length) {
	g_bInputInvalid = false;
	if(numbers == NULL || length <= 0)
		g_bInputInvalid = true;

	return g_bInputInvalid;
}

void MyGetLeastNumbers(int* data, int length, int k) {
	if(CheckInvalidArray(data, length))
		return;

	if(k > length) k = length;

	int start=0, end=length-1;
	int index = Partition(data, length, start, end);
	while(index != k-1) {
		if(index > k-1) {
			end = index - 1;
			index = Partition(data, length, start, end);
		}
		else {
			start = index + 1;
			index = Partition(data, length, start, end);
		}
	}

	PrintArrayFromI2J(data, 0, k-1);
}

// ==================== 1====================
void GetLeastNumbers_Solution1(int* input, int n, int* output, int k)
{
    if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
        return;

    int start = 0;
    int end = n - 1;
    int index = Partition(input, n, start, end);
    while(index != k - 1)
    {
        if(index > k - 1)
        {
            end = index - 1;
            index = Partition(input, n, start, end);
        }
        else
        {
            start = index + 1;
            index = Partition(input, n, start, end);
        }
    }

    for(int i = 0; i < k; ++i)
        output[i] = input[i];
}

//====================Solution2======================
typedef std::multiset<int, std::greater<int> > intSet;
typedef std::multiset<int, std::greater<int> >::iterator setIterator;
void GetLeastNumbers_Solution2(const std::vector<int>& data, intSet& leastNumbers, int k) {
	leastNumbers.clear();

	if(k < 1 || data.size() < k)
		return;

	std::vector<int>::const_iterator iter = data.begin();
	for(; iter != data.end(); ++iter) {
		if(leastNumbers.size() < k)
			leastNumbers.insert(*iter);
		else {
			setIterator iterGreatest = leastNumbers.begin();

			if(*iter < *iterGreatest) {
				leastNumbers.erase(iterGreatest);
				leastNumbers.insert(*iter);
			}
		}
	}
}

// ==================== ====================
void Test(char* testName, int* data, int n, int* expectedResult, int k)
{
    if(testName != NULL)
        printf("%s begins: 
", testName);

    std::vector<int> vectorData;
    for(int i = 0; i < n; ++ i)
        vectorData.push_back(data[i]);

    if(expectedResult == NULL)
        printf("The input is invalid, we don't expect any result.
");
    else
    {
        printf("Expected result: 
");
        for(int i = 0; i < k; ++ i)
            printf("%d\t", expectedResult[i]);
        printf("
");
    }

//    printf("Result for MySolution:
");
//    MyGetLeastNumbers(data, n, k);

//    printf("Result for solution1:
");
//    int* output = new int[k];
//    GetLeastNumbers_Solution1(data, n, output, k);
//    if(expectedResult != NULL)
//    {
//        for(int i = 0; i < k; ++ i)
//            printf("%d\t", output[i]);
//        printf("
");
//    }
//
//    delete[] output;
//
    printf("Result for solution2:
");
    intSet leastNumbers;
    GetLeastNumbers_Solution2(vectorData, leastNumbers, k);
    printf("The actual output numbers are:
");
    for(setIterator iter = leastNumbers.begin(); iter != leastNumbers.end(); ++iter)
        printf("%d\t", *iter);
    printf("

");
}

// k 
void Test1()
{
    int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
    int expected[] = {1, 2, 3, 4};
    Test("Test1", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));
}

// k 
void Test2()
{
    int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
    int expected[] = {1, 2, 3, 4, 5, 6, 7, 8};
    Test("Test2", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));
}

// k 
void Test3()
{
    int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
    int* expected = NULL;
    Test("Test3", data, sizeof(data) / sizeof(int), expected, 10);
}

// k 1
void Test4()
{
    int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
    int expected[] = {1};
    Test("Test4", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));
}

// k 0
void Test5()
{
    int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
    int* expected = NULL;
    Test("Test5", data, sizeof(data) / sizeof(int), expected, 0);
}

//  
void Test6()
{
    int data[] = {4, 5, 1, 6, 2, 7, 2, 8};
    int expected[] = {1, 2};
    Test("Test6", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));
}

//  
void Test7()
{
    int* expected = NULL;
    Test("Test7", NULL, NULL, expected, 0);
}

int main(int argc, char* argv[])
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();

    return 0;
}