数组的常用算法(2) - boolean数组的灵活应用

90 阅读 0 评论 60 点赞

我是靠谱客的博主忧虑豌豆，最近开发中收集的这篇文章主要介绍数组的常用算法(2) - boolean数组的灵活应用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在《数组的常用算法(1)》 http://blog.csdn.net/b_miracle6/article/details/47111059 里，初步尝试了如何利用数组值与数组脚标的对应关系，并以boolean数组为工具的算法。

我们常常习惯用int, double, String等来建立数组，其实boolean数组在简化代码方面有很好的效果。

拿一个老掉牙的素数问题来做例子：从command line读入一个数字N, 输出出从0~N的所有素数

一般思路：

1. 遍历2~N，用method boolean isPrime(int x)来判断是否为素数，是就打印输出；

2. 在isPrime(int x)里

- 如果x是偶数，则肯定是合数，返回值为false;

- 如果x是奇数，则用从3开始的奇数去除x, 若能整除，说明也是合数，返回值为false

* 这里有一个小的数学窍门，除数选择不必从3一直到x，只需要到x的平方根就可以了（具体证明看数学书）

根据以上思路写出来的代码：

public class PrimeV1{
public static void main(String[] args) {
int N
= Integer.parseInt(args[0]);
for(int i = 2; i <= N; i++){
if(isPrime(i))
System.out.print(i + " ");
}
System.out.println();
}
private static boolean isPrime(int x){
boolean isPrime = true;
//all even numbers are not prime
if(x % 2 == 0 && x != 2)
isPrime = false;
//remaining numbers are odd, if one odd can be diviede by another odd number, it is not prime
else{
for(int i = 3; i * i <= x; i+=2) {
if(x % i == 0){
isPrime = false;
break;
}
}
}
return isPrime;
}
}

使用int数组存放素数的思路：

1. 建一个数组int[ ] primes来存放N以内的素数(第一个元素当然是2了）；

2. 利用int count来追踪这个数组里已有的素数个数

3. 利用一个嵌套循环，外循环是判断从3~N的整数，如果是素数就加到数组primes里，同时更新count值；内循环是判断某个整数，如果是合数就开始下一轮外部循环

public class PrimeV2{
public static void main(String[] args) {
int N
= Integer.parseInt(args[0]);
int[] primes = new int[N];
primes[0] = 2; //the first element is 2
int count = 1; // # of primes in the array primes
LOOP:
for(int x = 3; x < N; x++){
for (int i = 0; i < count; i++){
if(x % primes[i] == 0)
continue LOOP;
}
primes[count++]	= x;
}
for(int i = 0; i < count; i++)
System.out.print(primes[i] + " ");
System.out.println();
}
}

使用boolean数组的思路：

* 解法中用到了数学里著名的埃拉托斯特尼筛子，请参考 http://mathworld.wolfram.com/SieveofEratosthenes.html

** 整个解法里利用了boolean数组脚标和0~N之间整数的关系

1. 建立一个boolean数组boolean[ ] isPrime

2. 先假设所有的整数都是素数，即数组isPrime[]每个元素都为true

3. 用埃拉索斯特尼筛子把合数挑出来标记为false

4. 输出数组isPrime[]里标记仍为true的元素的脚标

public class PrimeSieve {
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
//initially assume all integers are prime
boolean[] isPrime = new boolean[N+1];
for(int i = 2; i <= N; i++)
isPrime[i] = true;
// mark non-primes <= N using sieve of Eratosthenes
for(int i = 2; i <= Math.sqrt(N); i++){
// if i is prime, then mark multiples of i as nonprime
// suffices to consider multiples i, i+1, ..., N/i
if (isPrime[i]) {
for(int j = i; i*j <= N; j++)
isPrime[i*j] = false;
}
}
//count primes
int primes = 0;
for(int i = 2; i <= N; i++)	{
if(isPrime[i]) {
System.out.print(i + " ");
primes++;
}
}
System.out.println();
System.out.println("The number of primes <= " + N + " is " + primes);
}
}