算法：递归和分治-实战
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_43126117/article/details/99105076
leetcode:50实现 pow(x, n) ，即计算 x 的 n 次幂函数。
方法一、直接调用库函数
我猜运行时间是最快的
public double myPow(double x, int n) {
return Math.pow(x, n);
}方法二、暴力
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1;
for (long i = 0; i < N; i++)
ans = ans * x;
return ans;
}方法三、递归分治的做法
class Solution {
private double fastPow(double x, long n) {
if (n == 0) {
return 1.0;
}
double half = fastPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return fastPow(x, N);
}
};leetcode:169求众数。
题目解析：本质就是求数组，相同元素出现次数，返回的结果就是次数最多对应的元素。
方法一：暴力
public int majorityElement1(int[] nums) {
int n = nums.length;
for (int x : nums) {
int count = 0;
for (int j : nums) {
if (x == j) count++;
}
if (count > n / 2) return x;
}
return 0;
}方法二：哈希表 ，元素出现次数存入map中
public int majorityElement2(int[] nums) {
int n = nums.length;
Map<Integer, Integer> map = new HashMap();
for (int x : nums) {
Integer num = map.get(x);
if (num == null) num = 0;
map.put(x, num + 1);
if (num + 1 > n / 2) return x;
}
return 0;
}方法三：分治
class Solution11 {
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 majority(int[] nums, int lo, int hi) {
if (lo == hi) { //递归出口
return nums[lo];
}
//数据准备
int mid = (hi-lo)/2 + lo;
//对子问题进行递归处理
int left = majority(nums, lo, mid);
int right = majority(nums, mid+1, hi);
//子结果数据合并判断
if (left == right) {
return left;
}
//left!=right时，根据次数判断
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 majority(nums, 0, nums.length-1);
}
}方法四：扩展 Boyer-Moore 投票算法
假设众数为当前值记为+1，其余数记为-1，并且相加，当等于零时，重新开始，假设下一个为众数，直到最后，结果肯定大于0，那么最后一个假设众数为真。
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-09-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录