网易笔试——混合颜料

你就是一个画家！你现在想绘制一幅画，但是你现在没有足够颜色的颜料。为了让问题简单，我们用正整数表示不同颜色的颜料。你知道这幅画需要的n种颜色的颜料，你现在可以去商店购买一些颜料，但是商店不能保证能供应所有颜色的颜料，所以你需要自己混合一些颜料。混合两种不一样的颜色A和颜色B颜料可以产生 (A XOR B)这种颜色的颜料(新产生的颜料也可以用作继续混合产生新的颜色,XOR表示异或操作)。本着勤俭节约的精神，你想购买更少的颜料就满足要求，所以兼职程序员的你需要编程来计算出最少需要购买几种颜色的颜料？

输入描述:

第一行为绘制这幅画需要的颜色种数n (1 ≤ n ≤ 50)
第二行为n个数x

(1 ≤ x

 ≤ 1,000,000,000)，表示需要的各种颜料.

输出描述:

输出最少需要在商店购买的颜料颜色种数，注意可能购买的颜色不一定会使用在画中，只是为了产生新的颜色。

输入例子:

3
1 7 3

输出例子:

解题思路：

由于a^b=c那么a^c=b，a^a=0，最早的思路是将colors[]数组里的元素及其^的所有可能值全部放到一个Map里，然后找到Map里的最小不相交子集（就是里面的任何一个元素不能由其他元素通过^生成），但是后来发现空间复杂度都在O（Nⁿ）。

后来发现一条规律，就是0001,0010,0100,1000，可以通过^生成任意4位的数字，那么本题的答案不会超过32（int的长度）

再后来想到高斯消元和最小线性无关组就有了自己的思路。首先将数组排序，获取最高位的1，每次将最高位的1进行^运算，使得数组里面从后往前数最高位每个1只保留一个，最终得到类似于{0,0,00000001,00000011，00011000,00100010}这样的结构，那么答案就出来了。

Java实现:

package com.tonyluis;

import java.util.*;

public class NeteaseSolution3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			final int SUM = in.nextInt();
			int[] colors = new int[SUM];
			for (int i = 0; i < SUM; i++)
				colors[i] = in.nextInt();
			Arrays.sort(colors);
			System.out.println(minColor(colors));
		}
	}

	static int minColor(int[] colors) {
		int max = 1 << 30;
		int right = colors.length - 1;
		while (right >= 0 && colors[right] != 0) {
			while (max > colors[right])
				max >>= 1;
			while (right > 0 && colors[right - 1] >= max) {
				colors[right - 1] ^= colors[right];
				insertSort(colors, right - 1);
			}
			right--;
		}
		return right >= 0 ? colors.length - right - 1 : colors.length;
	}

	// 将一个数插入到有序数组中 ArrayList底层使用数组实现，不如直接使用数组
	// 使用LinkedList可以减少直接插入排序的移位操作
	static void insertSort(int[] nums, int index) {
		int temp = nums[index];
		if (temp <= nums[0]) {
			for (int i = index; i > 0; i--)
				nums[i] = nums[i - 1];
			nums[0] = temp;
			return;
		}
		for (int i = index - 1; i >= 0; i--) {
			if (temp > nums[i]) {
				for (int j = index; j > i + 1; j--)
					nums[j] = nums[j - 1];
				nums[i + 1] = temp;
				return;
			}
		}
	}
}