题解 | #素数伴侣#典型的匈牙利算法---方便自己看
素数伴侣
https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e
import java.util.ArrayList; import java.util.List; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 获取输入的正整数个数 int n = in.nextInt(); // 定义一个集合,用于存放这n个正整数中奇数 List<Integer> jishu = new ArrayList<>(); // 定义一个集合,用于存放这n个正整数中的偶数 List<Integer> oushu = new ArrayList<>(); // 读取输入的正整数 for (int i = 0; i < n; i++) { int m = in.nextInt(); if (m % 2 == 0) { //偶数 oushu.add(m); } else { // 奇数 jishu.add(m); } } // 查找素数伴侣,返回查找到的最大对数 int max = findResult(jishu, oushu); // 输出最大对数 System.out.println(max); } /** * 查找n个正整数中存在素数伴侣的最大对数. */ private static int findResult(List<Integer> jishu, List<Integer> oushu) { // 定义找到的最大对数 int max = 0; // 定义一个数组,用于存放偶数的伴侣,这个数组里面存放的是奇数列表中的值,默认0填充 int[] oushuSoul = new int[oushu.size()]; // 对奇数进行遍历,判断该奇数能否找到偶数伴侣 for (int i = 0; i < jishu.size(); i++) { // 定义一个数组,用于存放偶数列表中的偶数是否被该奇数配对过 boolean[] isPair = new boolean[oushu.size()]; // 如果奇数和偶数能够形成最优配对,则max加1 if (isPairSuccess(jishu.get(i), oushu, oushuSoul, isPair)) { max++; } } return max; } /** * 判断奇数 jishu,是否能够在oushu列表中形成最优配对 */ private static boolean isPairSuccess(int jishu, List<Integer> oushu, int[] oushuSoul, boolean[] isPair) { // 将这个奇数依次与偶数进行配对,看是否存在最优配对 for (int i = 0; i < oushu.size(); i++) { // 如果两则相加为素数,切该位置还没有配对过,则可组成素数伴侣,但最优素数伴侣得继续进行条件判断 if (isPrimeNumber(jishu + oushu.get(i)) && isPair[i] == false) { // 将该偶数设置为已配对过 isPair[i] = true; // 匈牙利算法,先到先得,能让就让;如果该位置的偶数还没有奇数伴侣,则形成最佳素数伴侣(先到先得); // 如果该位置偶数已经有了奇数伴侣,那么就看这个奇数是否还能找到其他的偶数伴侣,如果能找到, // 就将该位置偶数让出(能让就让) if (oushuSoul[i] == 0 || isPairSuccess(oushuSoul[i], oushu, oushuSoul, isPair)) { // 将该位置偶数伴侣添加到数组进行配对成功 oushuSoul[i] = jishu; // 找到最优的素数伴侣了 return true; } } } return false; } /** * 判断一个数是否为素数. * 质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数 */ private static boolean isPrimeNumber(int num) { for (int i = 2; i < num; i++) { // 在2-num之间,只要存在一个数,使得num能被这个数整除,则num为非素数 if (num % i == 0 ) { return false; } } // 上面没有返回false,则表明不存在一个数,使得num能被这个数整除,则num为素数,则返回true return true; } }