目的
程序 = 数据结构 + 算法
了解数据结构、算法思想、优缺点、合理运用到项目中， 常见算法：
时间复杂度：
O(1) -> HashMap
O(logn)-> 二叉树
O(n) -> for 循环
O(nlogn) -> for循环嵌套二叉树 、 Arrays.sort
O(n2) -> for循环嵌套
…
时间复杂度由小 到大为：
O(1) < O(log2n) < O(n) < O(n log2n) <O(n2)<O(n3) …<O(2n)<O(n!)
一、算法之二分法
1.二分法查找
有序的数组，效率 O(logn)
实例： 猜数字 100 ，需要猜多少次 （log128)
对数与幂运算互为逆运算。（幂运算表示指数个底数相乘）
1.1 常用有序数据查找
public class BinaryTest
{
public static int binary(int[] array, int value)
{
if(array == null || array.length ==0)
{
return -1;
}
int start = 0;
int end = array.length - 1;
int middle;
while(start+1 < end)
{
middle = start+(end - start) / 2;
if(value == array[middle])
{
return middle;
}
if(value > array[middle])
{
start = middle;
}
if(value < array[middle])
{
end = middle;
}
}
if(value==array[start])
{
return start;
}
if(value==array[end])
{
return end;
}
return -1;
}
public static void main(String[] args)
{
int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int value = binary(a, 9);
System.out.println(value);
}
}
1.2 旋转有序数组排序 （无重复数组）
//数学： 2、4象限 通用
public class BinaryTest
{
public static int binary(int[] array, int value)
{
if(array == null || array.length ==0)
{
return -1;
}
int start = 0;
int end = array.length - 1;
int middle;
while(start+1 < end)
{
//middle 随着start、end 变化而变化
middle = start+(end - start) / 2;
if(value == array[middle])
{
return middle;
}
//确定升序，还是降序
if(array[middle] > array[start])//升序
{
//在start 和 middle
if(value <= array[middle] && value>=array[start])
{
end = middle;
}else
{
start = middle;
}
}
else
{
if(value >=array[middle] && value <=array[end])
{
start = middle;
}
else
{
end =middle;
}
}
}
if(value==array[start])
{
return start;
}
if(value==array[end])
{
return end;
}
return -1;
}
public static void main(String[] args)
{
int[] a = { 7, 8, 9,1, 2, 3, 4, 5, 6};
int value = binary(a, 9);
System.out.println(value);
}
}
1.3 在旋转有序数组中最小值 (无重复数组)
class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int start = 0;
int end = nums.length - 1;
int mid;
while (start + 1 < end ) {
mid = start + (end - start) / 2;
//正序
if (nums[mid] >= nums[start]) {
if (nums[end] <= nums[mid]) {
start = mid;
} else {
end = mid;
}
} else {
//end =mid; ??
start = mid;
}
}
return Math.min(nums[start], nums[end]);
}
}
1.4 找峰值元素
class solution1{
public int findPeakElement(int[] nums)
{
if(nums == null || nums.length==0)
{
return -1;
}
int start = 0;
int end = nums.length -1;
int mid;
while(start+1 < end)
{
mid = start + (end-start)/2;
if(nums[mid]<nums[mid-1])
{
end= mid;
}
else if(nums[mid]<nums[mid+1])
{
start = mid;
}
else
{
return mid;
}
}
return nums[start]>nums[end] ? start:end;
}
}
1.5 切木头
public class CutWood {
public static void main(String[] args) {
int[] nums = {612, 301, 257, 900};
System.out.println(new CutWood().cutWood(nums, 10));
}
/**
* 将一堆木头切成指定的块数，求出单块木头最大长度
*
* @param nums 木头集合
* @param k 块数
* @return 单块木头最大长度
*/
public int cutWood(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int start = 1;
int end = getMax(nums);
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
int pieces = getPieces(nums, mid);
//能够切分，但不一定是单个最长的木头
if (pieces > k) {
start = mid;
} else {
end = mid;
}
}
if (getPieces(nums, start) >= k) {
return start;
}
if (getPieces(nums, end) >= k) {
return end;
}
return 0;
}
private int getPieces(int[] nums, int mid) {
int pieces = 0;
for (int num : nums) {
pieces += num / mid;
}
return pieces;
}
private int getMax(int[] nums) {
int max = 0;
for (int num : nums) {
if (num > max) {
max = num;
}
}
return max;
}
}
//输出结果为 153
2 双指针（二分法）
- 确定是求位置、索引、还是具体数字
2.1 两个数之和等于固定数值
分析：
1. 常规算法，双for循环嵌套，时间复杂度为：n<sup>2</sup>
2. 采用双指针将时间复杂度降为 n
public class TwoSum {
public static void main(String[] args) {
int[] nums ={1,3,4,6,7,8,12,15,19};
int[] ret =new TwoSum().twoSum(nums,28);
for(int i:ret) {
System.out.println(i);
}
}
/**
* 两数求和 ，要求时间复杂度为 0（n)
* @param nums 有序集合
* @param val 目标
* @return 结果 (注意返回的不是数组索引) --> 索引 +1
*/
public int[] twoSum(int[] nums, int val) {
//存放结果
int[] result = {-1, -1};
if (nums == null || nums.length == 0) {
return result;
}
int start = 0;
int end = nums.length - 1;
while (start < end) {
if (nums[start] + nums[end] < val) {
start++;
} else if (nums[start] + nums[end] > val) {
end--;
} else {
result[0] = start + 1;
result[1] = end + 1;
break;
}
}
return result;
}
}
2.2 三个数之和等于固定值
分析：
1. 常规算法，三层for循环嵌套，时间复杂度为：n3 2. 采用双指针将时间复杂度降为 n2public class ThreeSum {
public static void main(String[] args) {
int[] nums = {-1, 0, -1, 2, 1, 3, 4};
List<List<Integer>> ret = new ThreeSum().threeSum(nums);
if (ret == null || ret.size() == 0) {
System.out.println("not found");
} else {
System.out.println(ret.toString());
}
}
/**
* 三个数之后为0
*
* @param nums 集合
* @return 结果
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) {
return result;
}
//nlog(n)
Arrays.sort(nums);
int len = nums.length;
// 固定某一值，然后其余两个值采用双指针求和。
for (int i = 0; i < len - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = len - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] == 0) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
left++;
right--;
result.add(list);
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (nums[i] + nums[left] + nums[right] > 0) {
right--;
} else {
left++;
}
}
}
return result;
}
}
2.3 存水问题
/**
* 存水问题 (双指针问题）如果单边循环，不能确定下一步能存多少水
*/
public class TrapRainWater {
public static void main(String[] args) {
int[] nums = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println(new TrapRainWater().trapWater(nums));
}
public int trapWater(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int left = 0;
int right = nums.length - 1;
int leftH = nums[left];
int rightH = nums[right];
int sum = 0;
while (left < right) {
//Note
if (leftH < rightH) {
if (leftH > nums[left + 1]) {
sum += leftH - nums[left + 1];
} else {
leftH = nums[left + 1];
}
left++;
} else {
if (rightH > nums[right - 1]) {
sum += rightH - nums[right - 1];
} else {
rightH = nums[right - 1];
}
right--;
}
}
return sum;
}
}
2.4 有效三角形个数
//类比： 三个数求和
class solution{
public int triangleNumber(int[] nums) {
if(nums == null || nums.length ==0)
{
return 0;
}
Arrays.sort(nums);
int total =0;
for(int k =nums.length -1;k>=2;k--)
{
//固定一边
int start =0;
int end = k -1;
while(start < end)
{
if(nums[start] + nums[end] > nums[k])
{
total += end -start;
end --;
}
else
{
start ++;
}
}
}
return total;
}
}
参考
«算法图解»
- ”程序员小灰“ 公众号 (推荐)
- 示例 ：https://gitee.com/xushj/algorithm.git