分治思想
Dreams
|
310
|
0

799 字
|
12 分钟

1.基本概述

分治是一种算法设计策略，将问题分解成更小的子问题，然后分别解决这些子问题，最后将子问题的解合并起来得到原问题的解。这种策略常用于解决复杂问题，例如快速排序和归并排序就是基于分治思想设计的排序算法。

以下就是采用分治的思想。

2.快速选择算法

快速选择算法是一种选择第 k 小（或第 k 大）元素的算法，它基于快速排序算法的思想。它选择一个基准元素，然后将数组分为两部分：小于基准元素的部分和大于基准元素的部分。然后根据 k 与基准元素所在的位置的关系，选择继续在左边或右边递归查找，直到找到第 k 小（或第 k 大）的元素。这个算法的平均时间复杂度为 O(n)，其中 n 是数组的长度。

求排在第 i 名的元素

比如求排在第 i 名的元素，i 从 日 开始，由小到大排

简单方法就是先排序再选择

Arrays.sort(array);
return array[i];

但是时间复杂度是n*log(n)

使用快速选择算法

package com.dreams.divideandconquer;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 快速选择算法 - 分而治之
 */
public class QuickSelect {
    static int quick(int[] array, int left, int right, int i) {
        int p = partition(array, left, right); // 基准点元素索引值
        if (p == i) {
            return array[p];
        }
        if(i < p) { // 到左边找
            return quick(array, left, p - 1, i);
        } else { // 到右边找
            return quick(array, p + 1, right, i);
        }
    }

    public static void main(String[] args) {
        int[] array = {6, 5, 1, 2, 4};
        System.out.println(quick(array, 0, array.length - 1, 0)); // 1
    }

    static int partition(int[] a, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        // [0~9] right-left+1=3 [0,2]+4=[4,6]
        swap(a, idx, left);
        int pv = a[left];
        int i = left;
        int j = right;
        while (i < j) {
            // 1. j 从右向左找小(等)的
            while (i < j && a[j] > pv) {
                j--;
            }
            // 2. i 从左向右找大的
            while (i < j && a[i] <= pv) {
                i++;
            }
            // 3. 交换位置
            swap(a, i, j);
        }
        swap(a, left, i);
        return i;
    }

    static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

 

求数组中第K大的元素

使用上面的快速选择算法即可。

package com.dreams.divideandconquer;

import java.util.concurrent.ThreadLocalRandom;

/**
 * 求数组中第 K 大的元素
 */
public class Leetcode215 {

    public int findKthLargest(int[] a, int k) {
        return quick(
                a, 0, a.length - 1, a.length - k
        );
    }

    static int quick(int[] array, int left, int right, int i) {
        int p = partition(array, left, right); // 基准点元素索引值
        if (p == i) {
            return array[p];
        }
        if(i < p) { // 到左边找
            return quick(array, left, p - 1, i);
        } else { // 到右边找
            return quick(array, p + 1, right, i);
        }
    }

    static int partition(int[] a, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        // [0~9] right-left+1=3 [0,2]+4=[4,6]
        swap(a, idx, left);
        int pv = a[left];
        int i = left;
        int j = right;
        while (i < j) {
            // 1. j 从右向左找小(等)的
            while (i < j && a[j] > pv) {
                j--;
            }
            // 2. i 从左向右找大的
            while (i < j && a[i] <= pv) {
                i++;
            }
            // 3. 交换位置
            swap(a, i, j);
        }
        swap(a, left, i);
        return i;
    }

    static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        Leetcode215 code = new Leetcode215();
        // 应为5
        System.out.println(code.findKthLargest(new int[]{2, 1, 4, 5, 6}, 2));
    }
}

不过注意的是最坏的情况下会达到o(n^2)

 

数组中的中位数

代码：

package com.dreams.divideandconquer;

import java.util.concurrent.ThreadLocalRandom;

/**
 * 数组中的中位数
 */
public class FindMedian {
    public static double findMedian(int[] nums) {
        if (nums.length % 2 == 1) { // 奇数
            return quick(nums, 0, nums.length - 1, nums.length / 2);
        } else { // 偶数
            int x = quick(nums, 0, nums.length - 1, nums.length / 2);
            int y = quick(nums, 0, nums.length - 1, nums.length / 2 - 1);
            return (x + y) / 2.0;
        }
    }

    static int quick(int[] array, int left, int right, int i) {
        int p = partition(array, left, right); // 基准点元素索引值
        if (p == i) {
            return array[p];
        }
        if(i < p) { // 到左边找
            return quick(array, left, p - 1, i);
        } else { // 到右边找
            return quick(array, p + 1, right, i);
        }
    }

    static int partition(int[] a, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        // [0~9] right-left+1=3 [0,2]+4=[4,6]
        swap(a, idx, left);
        int pv = a[left];
        int i = left;
        int j = right;
        while (i < j) {
            // 1. j 从右向左找小(等)的
            while (i < j && a[j] > pv) {
                j--;
            }
            // 2. i 从左向右找大的
            while (i < j && a[i] <= pv) {
                i++;
            }
            // 3. 交换位置
            swap(a, i, j);
        }
        swap(a, left, i);
        return i;
    }

    static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    
    
    public static void main(String[] args) {
        System.out.println(findMedian(new int[]{4, 5, 1}));
    }


}

 

3.快速幂

比如求解a^11次方

就等价与a*a^5*a^5

Pow(x, n)

package com.dreams.divideandconquer;

/**
 * 快速幂
 */
public class QuickPowLeetcode50 {

    static double myPow(double x, int n) {
        long p = n; // -2
        if (p < 0) {
            p = -p; // -2147483648  2147483647
        }
        double r = myPowPositive(x, p);
        // 负数使用倒数
        return n < 0 ? 1 / r : r;
    }

    static double myPowPositive(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        if (n == 1) {
            return x;
        }
        double y = myPowPositive(x, n / 2);
        if ((n & 1) == 0) { // 偶数
            return y * y;
        } else { // 奇数
            return x * y * y;
        }
    }

    public static void main(String[] args) {
        System.out.println(myPow(2, 16));  // 65536
        System.out.println(myPow(2, 10));  // 1024
        System.out.println(myPow(2, 0)); // 1.0
        System.out.println(myPow(2, -2)); // 0.25    2^-2 = 1/2^2
        System.out.println(myPow(2, -2147483648)); // 1.0   int
    }
}

 

x 的平方根

代码：

package com.dreams.divideandconquer;

/**
 * 平方根整数部分
 */
public class Leetcode69 {

    static int mySqrt(int x) {
        int i = 1, j = x;
        int r = 0;
        while (i <= j) {
            int m = (i + j) >>> 1;
            // 不使用int mm = m * m，避免int越界
            if (m <= x / m) {
                i = m + 1;
                r = m;
            } else {
                j = m - 1;
            }
        }
        return r;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(99)); // 9
        System.out.println(mySqrt(1)); // 1
        System.out.println(mySqrt(2147395599));
    }
}

 

 

至少有 K 个重复字符的最长子串

统计字符串中每个字符的出现次数，移除哪些出现次数 < k 的字符，剩余的子串，递归做此处理，直至整个子串长度 < k (排除)，子串中没有出现次数 < k 的字符。

步骤：

  1. 首先检查整个字符串的长度是否小于 k，如果是，则返回 0，因为无法找到满足条件的子串。
  2. 创建一个长度为 26 的数组 counts，用于记录字符串中每个字符的出现次数。
  3. 遍历字符串，统计每个字符出现的次数，并存储在 counts 数组中。
  4. 然后遍历字符串，对于每个字符，如果它出现的次数大于 0 且小于 k，则进入一个 while 循环，寻找下一个满足条件的字符的位置。将原始字符串分割成两部分，分别递归处理。
  5. 递归调用 longestSubstring 函数，分别处理左半部分和右半部分，并返回两者中的最大值。
  6. 如果没有出现任何出现次数小于 k 的字符，直接返回字符串的长度。

代码：

package com.dreams.divideandconquer;

/**
 * 至少k个字符的最长子串
 */
public class Leetcode395 {
    static int longestSubstring(String s, int k) {
        // 子串落选情况
        if (s.length() < k) {
            return 0;
        }
        int[] counts = new int[26]; // 索引对应字符 值用来存储该字符出现了几次
        char[] chars = s.toCharArray();
        for (char c : chars) { // 'a' -> 0  'b' -> 1 ....
            counts[c - 'a']++;
        }
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            int count = counts[c - 'a']; // i字符出现次数
            if (count > 0 && count < k) {
                int j = i + 1;
                while(j < s.length() && counts[chars[j] - 'a'] < k) {
                    j++;
                }
                return Integer.max(
                        longestSubstring(s.substring(0, i), k),
                        longestSubstring(s.substring(j), k)
                );
            }
        }
        // 子串入选情况
        return s.length();
    }


    public static void main(String[] args) {
        System.out.println(longestSubstring("ddddaaa", 3));
        System.out.println(longestSubstring("ddaaa", 3));
    }
}

 

 

参考

黑马数据结构

暂无评论

发送评论 编辑评论

 
 
 
 
 
   
 
  
  
   
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
  
上一篇
下一篇 
  推荐文章
解决/A/:id 跳转到另一个/A/:id
 
git无法提交大文件
 
CSRF引起整合 SpringSecurity 发送POST请求出现 403