欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java 全排列的幾種實現(xiàn)方法

 更新時間:2024年11月26日 11:14:50   作者:飛滕人生TYF  
本文詳細(xì)介紹了Java中全排列問題的幾種實現(xiàn)方法,包括回溯法、字典序排列法和迭代法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

全排列問題是一個經(jīng)典的算法問題,指的是對一個序列中的所有元素生成不重復(fù)的排列組合。以下是全排列問題在 Java 中的詳細(xì)實現(xiàn)和講解。

1. 全排列問題定義

輸入: 給定一個序列或數(shù)組,找出所有元素的排列。
輸出: 返回所有可能的排列。

示例:

輸入:[1, 2, 3]

輸出:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

2. 常用算法

全排列的常見實現(xiàn)方法:

  • 回溯法(Backtracking)
  • 字典序排列法(Lexicographic Order)
  • 迭代法(非遞歸實現(xiàn))

3. 使用回溯法解決全排列

回溯法是一種基于遞歸的搜索算法,它通過不斷嘗試并撤銷之前的選擇來生成所有可能的解。

3.1 回溯法實現(xiàn)(基礎(chǔ)版)

適用于數(shù)組中無重復(fù)元素的全排列。

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length]; // 標(biāo)記是否使用過
        List<Integer> current = new ArrayList<>();
        backtrack(nums, used, current, result);
        return result;
    }

    private static void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
        // 終止條件:當(dāng)前排列的大小等于數(shù)組長度
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current)); // 將當(dāng)前排列加入結(jié)果
            return;
        }
        // 遍歷每個元素
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) { // 跳過已使用的元素
                continue;
            }
            // 做選擇
            current.add(nums[i]);
            used[i] = true;
            // 遞歸
            backtrack(nums, used, current, result);
            // 撤銷選擇
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = permute(nums);
        System.out.println(permutations);
    }
}

輸出結(jié)果

對于輸入 [1, 2, 3]

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

3.2 回溯法(不使用標(biāo)記數(shù)組)

通過交換數(shù)組中的元素,可以避免使用標(biāo)記數(shù)組。

import java.util.ArrayList;
import java.util.List;

public class PermutationsSwap {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, result);
        return result;
    }

    private static void backtrack(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i); // 交換元素
            backtrack(nums, start + 1, result);
            swap(nums, start, i); // 撤銷交換
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = permute(nums);
        System.out.println(permutations);
    }
}

3.3 回溯法處理重復(fù)元素

如果數(shù)組中包含重復(fù)元素(例如 [1, 1, 2]),我們需要對結(jié)果去重。可以通過對數(shù)組排序并在遞歸時跳過重復(fù)元素來實現(xiàn)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermutationsWithDuplicates {
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 排序以便跳過重復(fù)元素
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            // 跳過相鄰重復(fù)的元素
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            current.add(nums[i]);
            used[i] = true;
            backtrack(nums, used, current, result);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2};
        List<List<Integer>> permutations = permuteUnique(nums);
        System.out.println(permutations);
    }
}

輸出結(jié)果

對于輸入[1, 1, 2]

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

4. 字典序排列法

字典序法生成全排列的步驟:

  • 找到當(dāng)前排列的“最后一個升序?qū)?rdquo;。
  • 從右側(cè)找到比升序?qū)χ休^小值大的最小值,交換這兩個值。
  • 將右側(cè)部分反轉(zhuǎn)。

適用于需要按字典序輸出排列的情況。

import java.util.Arrays;

public class PermutationsLexicographic {
    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) { // 找到升序?qū)?
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j); // 交換
        }
        reverse(nums, i + 1); // 反轉(zhuǎn)后面的部分
    }

    private static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < 6; i++) {
            nextPermutation(nums);
            System.out.println(Arrays.toString(nums));
        }
    }
}

5. 總結(jié)

常見方法對比

方法適用場景特點
回溯法全排列(通用)最常用,適合生成所有排列,可以處理重復(fù)元素,通過遞歸和剪枝實現(xiàn)。
交換法無重復(fù)全排列不需要額外空間標(biāo)記數(shù)組,通過交換實現(xiàn)排列,但對重復(fù)元素需要額外處理。
字典序排列法字典序輸出排列按字典序生成排列,適合序列化輸出;需要對輸入序列進(jìn)行排序作為初始狀態(tài)。
迭代法生成排列的特定場景使用循環(huán)代替遞歸,但實現(xiàn)起來較為復(fù)雜,適合排列生成問題中的迭代優(yōu)化。

性能分析

  • 時間復(fù)雜度: O ( n ! ) O(n!) O(n!),每種方法
    的時間復(fù)雜度都與排列數(shù)量成正比。
  • 空間復(fù)雜度
    • 使用標(biāo)記數(shù)組的回溯法: O ( n ) O(n) O(n)
    • 使用交換法: O ( 1 ) O(1) O(1)(不包括遞歸棧)

全排列是算法中基礎(chǔ)而重要的問題?;厮莘ㄊ亲畛S玫慕鉀Q方式,而在實際開發(fā)中,根據(jù)不同的需求可以選擇合適的方法來實現(xiàn)高效的排列生成。

到此這篇關(guān)于Java 全排列的幾種實現(xiàn)方法的文章就介紹到這了,更多相關(guān)Java 全排列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • SpringMVC攔截器失效問題及解決方法

    SpringMVC攔截器失效問題及解決方法

    這篇文章主要介紹了SpringMVC?攔截器和異常處理器,以及SpringMVC攔截器失效分析解決方案,文中補(bǔ)充介紹了SpringMVC?攔截器和異常處理器的相關(guān)知識,需要的朋友可以參考下
    2024-01-01
  • 字節(jié)碼調(diào)教入口JVM?寄生插件javaagent

    字節(jié)碼調(diào)教入口JVM?寄生插件javaagent

    這篇文章主要介紹了字節(jié)碼調(diào)教入口JVM?寄生插件javaagent方法示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-08-08
  • 使用原生JDBC動態(tài)解析并獲取表格列名和數(shù)據(jù)的方法

    使用原生JDBC動態(tài)解析并獲取表格列名和數(shù)據(jù)的方法

    這篇文章主要介紹了使用原生JDBC動態(tài)解析并獲取表格列名和數(shù)據(jù),本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-08-08
  • 詳解Java子線程異常時主線程事務(wù)如何回滾

    詳解Java子線程異常時主線程事務(wù)如何回滾

    如果主線程向線程池提交了一個任務(wù),如果執(zhí)行這個任務(wù)過程中發(fā)生了異常,如何讓主線程捕獲到該異常并且進(jìn)行事務(wù)的回滾?本篇文章帶給你答案
    2022-03-03
  • Mybatis如何獲取insert新增數(shù)據(jù)id值

    Mybatis如何獲取insert新增數(shù)據(jù)id值

    這篇文章主要介紹了Mybatis如何獲取insert新增數(shù)據(jù)id值問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-05-05
  • 深入解析Java中volatile關(guān)鍵字的作用

    深入解析Java中volatile關(guān)鍵字的作用

    Java語言是支持多線程的,為了解決線程并發(fā)的問題,在語言內(nèi)部引入了 同步塊 和 volatile 關(guān)鍵字機(jī)制
    2013-09-09
  • Java.toCharArray()和charAt()的效率對比分析

    Java.toCharArray()和charAt()的效率對比分析

    這篇文章主要介紹了Java.toCharArray()和charAt()的效率對比分析,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-10-10
  • Java三種獲取redis的連接及redis_String類型演示(適合新手)

    Java三種獲取redis的連接及redis_String類型演示(適合新手)

    這篇文章主要介紹了Java三種獲取redis的連接及redis_String類型演示(適合新手),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-12-12
  • JavaGUI菜單欄與文本和密碼及文本域組件使用詳解

    JavaGUI菜單欄與文本和密碼及文本域組件使用詳解

    這篇文章主要介紹了JavaGUI菜單欄與文本和密碼及文本域組件使用,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)吧
    2023-03-03
  • Java中集合遍歷的方法示例代碼展示

    Java中集合遍歷的方法示例代碼展示

    在 Java 編程中,集合(Collection)是用于存儲和操作一組對象的重要工具,無論是數(shù)組、列表(List)、集合(Set),還是映射(Map),它們都提供了在不同場景下靈活使用的數(shù)據(jù)結(jié)構(gòu),這篇文章主要介紹了Java中集合遍歷的方法示例代碼展示,需要的朋友可以參考下
    2024-08-08

最新評論