基于partition函数解答某些编程题的思想

痛定思痛。 2022-02-02 07:09 84阅读 0赞

快速排序的核心就是partition函数，我们可以对该函数的接口作适当的改变，来运用修改过的partion函数解决一些编程算法。

这里举两个例子，这两个例子所用的partition函数如下所示：

int randomRange(int start,int end)
    {
    	return rand()%(end-start+1)+start;
    }
    int Partition(int input[],int length, int start,int end)
    {
    	if (input==NULL||length<=0||(end-start)>(length+1))
    		throw new std::bad_exception("Invalid Parameters");
    	int keyIndex=randomRange(start,end);
    	swap(input[keyIndex],input[start]);
    	int key=input[start];
    	int p=start;                    
    	int q=end+1;
    	for (;;)
    	{
    		do p++;while(p<end&&input[p]<key);
    		do q--;while(input[q]>key);	
    		if (p<q)
    			swap(input[p],input[q]);
    		else
    			break;
    	}
    	swap(input[start],input[q]);
    	return q;
    }

1、 最小的k个数，输入n个整数，找出其中最下的k个数，例如输入4、5、1、6、2、7、3、8、1、2，输出最下的4个数，则输出1、1、2、2。

这个题目运用partition函数进行求解就是仿照快速排序，不过快速排序分割后对前后两段继续进行分割，而这里需要判定分割的位置，然后再确定对前段还是后段进行分割。代码如下：

void GetLeastNumbers_by_partition(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];
    }

1、 数组中出现超过一半的数字，这一题就是《编程之美》上面寻找发帖水王的那题。

选择合适的判定条件进行递归，就可以求出结果，代码如下：

bool g_bInputInvalid = false;
    
    bool CheckInvalidArray(int* numbers, int length)
    {
        g_bInputInvalid = false;
        if(numbers == NULL && length <= 0)
            g_bInputInvalid = true;
    	
        return g_bInputInvalid;
    }
    
    bool CheckMoreThanHalf(int* numbers, int length, int number)
    {
        int times = 0;
        for(int i = 0; i < length; ++i)
        {
            if(numbers[i] == number)
                times++;
        }
    	
        bool isMoreThanHalf = true;
        if(times * 2 <= length)
        {
            g_bInputInvalid = true;
            isMoreThanHalf = false;
        }
    	
        return isMoreThanHalf;
    }
    int MoreThanHalfNum_Solution1(int* numbers, int length)
    {
        if(CheckInvalidArray(numbers, length))
            return 0;
    	
        int middle = length >> 1;
        int start = 0;
        int end = length - 1;
        int index = Partition(numbers, length, start, end);
        while(index != middle)
        {
            if(index > middle)
            {
                end = index - 1;
                index = Partition(numbers, length, start, end);
            }
            else
            {
                start = index + 1;
                index = Partition(numbers, length, start, end);
            }
        }
    	
        int result = numbers[middle];
        if(!CheckMoreThanHalf(numbers, length, result))
            result = 0;
    	
        return result;
    }

最后给出一个基本的测试函数：

int main()
    {
    
    	int a[10]={4,5,1,6,2,7,3,8,1,2};
    	int result[4]={0};
    	GetLeastNumbers_by_partition(a,10, result, 4);
    	for (int i=0;i<4;i++)
    		cout << result[i];
    	int b[10]={2,1,2,2,6,9,2,1,2,2};
    	int num=MoreThanHalfNum_Solution1(b,10);
    	cout <<endl<<num<<endl;
    	return 0;
    }

附录

关于上述的两个编程题，有更加好的解法，代码如下：

1、

typedef multiset<int, greater<int> >            intSet;
    typedef multiset<int, greater<int> >::iterator  setIterator;
    
    void GetLeastNumbers_Solution2(const vector<int>& data, intSet& leastNumbers, int k)
    {
        leastNumbers.clear();
    
        if(k < 1 || data.size() < k)
            return;
    
        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 < *(leastNumbers.begin()))
                {
                    leastNumbers.erase(iterGreatest);
                    leastNumbers.insert(*iter);
                }
            }
        }
    }

2、

int MoreThanHalfNum_Solution2(int* numbers, int length)
    {
        if(CheckInvalidArray(numbers, length))
            return 0;
     
        int result = numbers[0];
        int times = 1;
        for(int i = 1; i < length; ++i)
        {
            if(times == 0)
            {
                result = numbers[i];
                times = 1;
            }
            else if(numbers[i] == result)
                times++;
            else
                times--;
        }
     
        if(!CheckMoreThanHalf(numbers, length, result))
            result = 0;
     
        return result;
    }