现在的位置: 首页 > 综合 > 正文

位图的用法

2019年05月27日 ⁄ 综合 ⁄ 共 1295字 ⁄ 字号 评论关闭
public class DuplicatedArrayTest {
	public static void main(String[] args) {
		int[][] arr = { { 1, 2, 3, 5, 3, 5, 56, 534, 3, 32 }, { 1, 2, 3, 5 },
				{ 1, 2, 3, 5, 3, 5 }, { 0, 0, 1, 2, 3, 5, 56, 534, 78, 32 }, };
		for (int i = 0; i < arr.length; i++) {
			System.out.print(" 数组: ");
			for (int temp : arr[i]) {
				System.out.print(temp + ", ");
			}
			System.out.print(" 中 ");
			System.out.print(hasDuplicatedItem(arr[i]) ? " 存在 " : " 不存在 ");
			System.out.print(" 重复元素.\n ");
		}
	}

	/**
	 * 判断整形数组中是否有重复数据,时间复杂度为O(n)
	 * 
	 * @param arr
	 * @return
	 */
	public static boolean hasDuplicatedItem(int[] arr) {
		// 扫描数组找最大值
		int max = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		// 按最大值创建一个新数组
		int[] bitArray = new int[max + 1];
		// 按值向新数组中添值,如value为3则bitArray[3]=1
		
		for (int value : arr) {
			if (bitArray[value] != 0) {
				// 如果value指向的位置已经不是零,说明之前已经给这一块置1了,立即返回true表示数组有重复
				return true;
			} else {
				// value指向的位置是零,则置为1表示这一位已经有数存在了
				bitArray[value] = 1;
			}
		}
		return false;
	}
}

class BitmapSorter {
	public static void main(String[] args) {
		int[] arr = { 1, 7, -3, 0, 0, 6, 6, 9, -11 };
		bitmapSort(arr);
		for (int i : arr) {
			System.out.print(i + " , ");
		}
	}

	/**
	 * 使用位图法进行排序
	 * 
	 * @param arr
	 */
	public static void bitmapSort(int[] arr) {
		// 找出数组中最值
		int max = arr[0];
		int min = max;
		for (int i : arr) {
			if (max < i) {
				max = i;
			}
			if (min > i) {
				min = i;
			}
		}
		// 得到位图数组  -----实现有序
		int[] newArr = new int[max - min + 1];
		for (int i : arr) {
			int index = i - min;
			newArr[index]++;
		}
		// 重整arr中的元素   -------规整数组
		int index = 0;
		for (int i = 0; i < newArr.length; i++) {
			while (newArr[i] > 0) {
				arr[index] = i + min;
				index++;
				newArr[i]--;
			}
		}
	}
}

抱歉!评论已关闭.