赞
踩
将大问题分割成一个个小问题
分治策略:对于一个规模为n的问题,若该问题可以容易的解决(比如规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解决这些子问题,然后将各个子问题的解合并得到原问题的解。
在数组中出现次数大于数组长度的一半
依题意,不用判断数组为空,而且总是存在多数元素
那么如果将将数组分割一半,那么在这一半的数组中,多数元素依旧是新组数的多数元素
3 | 3 | 2 | 3 | 2 | 3 | 3 |
---|---|---|---|---|---|---|
3 | 1 | 2 | 3 | |||
2 | 3 | 3 | ||||
3 | 3 |
将数组分成长度为一的数组,此时每个数都是自身 数组的多数元素。(递)
每两个数组合并,出现次数多的,当作合并数组的多数元素。(归)
定义一个获取多数元素的方法,参数应该含有原理数组的值,他的起始位置,他的终止位置
当数组里只有一个数时将这个数返回
将数组一份为二,取出左边的多数元数,再取出右边的多数元素
如果左边的多数元素==右边的多数元素 就返回这个多数元素
else比较左边多数元素出现的次数,和右边多数元素出现的次数,返回出现次数多的多数元素
class Solution { private int countInRange(int[] nums, int num, int lo, int hi) { int count = 0; for (int i = lo; i <= hi; i++) { if (nums[i] == num) { count++; } } return count; } private int majorityElementRec(int[] nums, int lo, int hi) { if (lo == hi) { return nums[lo]; } int mid = (hi - lo) / 2 + lo; int left = majorityElementRec(nums, lo, mid); int right = majorityElementRec(nums, mid + 1, hi); if (left == right) { return left; } int leftCount = countInRange(nums, left, lo, hi); int rightCount = countInRange(nums, right, lo, hi); return leftCount > rightCount ? left : right; } public int majorityElement(int[] nums) { return majorityElementRec(nums, 0, nums.length - 1); } }
将数组分成长度为一的子数组,两两做比,找出最大和子数组将其返回。
将返回后的数组两两做比,找出最大和子数组将其返回。
class Solution { public class Status { public int lSum, rSum, mSum, iSum; public Status(int lSum, int rSum, int mSum, int iSum) { this.lSum = lSum; this.rSum = rSum; this.mSum = mSum; this.iSum = iSum; } } public int maxSubArray(int[] nums) { return getInfo(nums, 0, nums.length - 1).mSum; } public Status getInfo(int[] a, int l, int r) { if (l == r) { return new Status(a[l], a[l], a[l], a[l]); } int m = (l + r) >> 1; Status lSub = getInfo(a, l, m); Status rSub = getInfo(a, m + 1, r); return pushUp(lSub, rSub); } public Status pushUp(Status l, Status r) { int iSum = l.iSum + r.iSum; int lSum = Math.max(l.lSum, l.iSum + r.lSum); int rSum = Math.max(r.rSum, r.iSum + l.rSum); int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum); return new Status(lSum, rSum, mSum, iSum); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。