题目:春节期间小明使用微信红包群收到很多个红包非常开心。在查看领取红包记录时发现某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金額写出具体算法思路和代码实现,要求算法尽可能高效给定一个红包的金额数组gifts及它的大小n,请返回所求红包的金额若没有金额超過总数的一半,返回0
分析:将红包数组排序后,取中值若是与左右的值相等,则返回反之返回0。
第一种方法:采用快速排序
1.左右指针法实现思路:在一段区间内我们有一个值key,从左边区间进行遍历直到找到一个大于key的值就停下,然后再从右边找小于key的值找到一個也停下来。我们将左右的值进行交换这样左边那个大于key的值就被换到了右边,而右边那个比key小的值就被换到了左边当左右两个指针楿遇的时候就说明所有元素都与key做过了比较。然后再将左指针所在的元素赋值给key此时按照上述方法进行递归实现[left,
2.挖坑法的思想是类似于咗右指针法的,思路是先将最右边的值保存下来作为key值。这时候最右边的值被取出去最右边就相当于有了一个坑,我们从左向右进行遍历找到一个比key大的数就把它填到这个坑里,这时候就相当于坑在左边我们有从右向左进行遍历找比key小的数,找到后再次填到坑里依次类推,大致的思想和上面的解法其实是很相似的
第二种方法:采用冒泡排序。