《剑指offer》算法题第八天

今日题目（对应书上第39~42题）：

数组中出现次数超过一半的数字
最小的k个数（top k，重点！）
数据流中的中位数
连续子数组的最大和

今天的题目都比较经典，特别是第2题。

1. 数组中出现次数超过一半的数字

题目描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：
有两种方法，
一，利用类似于快排的思想，寻找数组中的中位数，然后再检查是否满足出现次数。
二，根据数组的特点来做。

代码如下：

 //方法一，快排

 public class Solution {

     public int MoreThanHalfNum_Solution(int [] array) {

         if(array.length == 0) return 0;

         int start = 0, end = array.length-1;

         int mid = array.length>>1;

         while(start < end){

             int ind = partition(array,start,end);

             if(ind == mid)

                 break;

             if(ind > mid)

                 end = ind-1;

             if(ind < mid)

                 start = ind+1;

         }

         if(check(array,array[mid]))

             return array[mid];

         else return 0;

     }

     public boolean check(int[] nums,int result){

         int times = 0;

         for(int n:nums){

             if(n == result)

                 times++;

         }

         return times*2 > nums.length;

     }

     public int partition(int[] nums,int start,int end){

         int target = nums[end];

         int res = start;

         for(int i = start; i < end; i++){

             if(nums[i] < target){

                 int swap = nums[i];

                 nums[i] = nums[res];

                 nums[res] = swap;

                 res++;

             }

         }

         nums[end] = nums[res];

         nums[res] = target;

         return res;

     }

 }

 //方法二

     public int MoreThanHalfNum_Solution(int [] array) {

         if(array.length == 0) return 0;

         int result = array[0];

         int times = 1;

         for(int n:array){

             if(times == 0){

                 result = n;

                 times = 1;

             }else if(result == n)

                 times++;

             else

                 times--;

         }

         if(check(array,result))

             return result;

         else return 0;

     }

2. 最小的k个数

题目描述：

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路：
这道题是经典的top K问题，有两种解法：
1,运用快排，找出第K个数的位置，将前面的数输出
2,利用容量为K的最大堆，循环数组，每次替换掉堆中最大的数

代码如下：

 //快排

 public class Solution {

     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

         ArrayList<Integer> res = new ArrayList();

         if(k > input.length || k == 0) return res;

         int start = 0, end = input.length-1;

         int ind = partition(input,start,end);

         while(ind != k-1){

             if(ind > k-1){

                 end = ind-1;

             }else{

                 start = ind+1;

             }

             ind = partition(input,start,end);

         }

         for(int i = 0;i < k; i++)

             res.add(input[i]);

         return res;

     }

     public int partition(int[] nums,int start,int end){

         int target = nums[end];

         int ind = start;

         for(int i = start; i < end;i++){

             if(nums[i] < target){

                 int swap = nums[i];

                 nums[i] = nums[ind];

                 nums[ind] = swap;

                 ind++;

             }

         }

         nums[end] = nums[ind];

         nums[ind] = target;

         return ind;

     }

 }

 //利用最大堆

 public class Solution {

     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

         if(k > input.length || k < 1) return new ArrayList();

         PriorityQueue<Integer> maxHeap = new PriorityQueue(k,new Comparator<Integer>(){

             public int compare(Integer o1,Integer o2){

                 return o2.compareTo(o1);

             }

         });

         for(int i = 0; i < input.length; i++){

             if(maxHeap.size() < k)

                 maxHeap.add(input[i]);

             else{

                 if(maxHeap.peek() > input[i]){

                     maxHeap.poll();

                     maxHeap.add(input[i]);

                 }

             }

         }

         return new ArrayList(maxHeap);

     }

 }

3.数据流中的中位数

题目描述：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

思路：
这道题的关键是选择一个怎样的数据结构来维护数据流，可以使插入和查询的速度都比较理想。在这边维护了一个最大堆和一个最小堆，最大堆存储中位数左边的数字，最小堆存储中位数右边的数字。

代码如下：

 public class Solution {

     int count = 0;

     PriorityQueue<Integer> min = new PriorityQueue();

     PriorityQueue<Integer> max = new PriorityQueue(new Comparator<Integer>(){

         public int compare(Integer o1,Integer o2){

             return o2-o1;

         }

     });

     public void Insert(Integer num) {

         if((count&1) == 0){

             min.offer(num);

             max.offer(min.poll());

         }else{

             max.offer(num);

             min.offer(max.poll());

         }

         count++;

     }

     public Double GetMedian() {

         if(((min.size()+max.size())&1) == 0)

             return (min.peek()+max.peek())/2.0;

         else

             return max.peek()*1.0;

     }

 }

4.连续子数组的最大和

题目描述：

输入一个整数数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

思路：
这道题也算是比较经典的一道题了，面经里面经常看到，下面给出两种解法。

代码如下：

 //解法一

 public class Solution {

     public int FindGreatestSumOfSubArray(int[] array) {

         int max = Integer.MIN_VALUE;

         int sum = 0;

         for(int n:array){

             if(sum <= 0)

                 sum = n;

             else

                 sum += n;

             max = max>sum?max:sum;

         }

         return max;

     }

 }

 //解法二，动态规划

 public class Solution {

     public int FindGreatestSumOfSubArray(int[] array) {

         int[] dp = new int[array.length];

         dp[0] = array[0];

         for(int i = 1; i < array.length; i++){

             if(dp[i-1] < 0)

                 dp[i] = array[i];

             else

                 dp[i] = array[i] + dp[i-1];

         }

         int res = dp[0];

         for(int n:dp)

             res = n>res?n:res;

         return res;

     }

 }

巴特西

《剑指offer》算法题第八天

最新文章

热门文章