算法设计:找出诚实的人
一个地方有两种人：诚实的人和骗子，诚实的人只说真话，骗子可能说真话也可能说假话，已知的是这里诚实的人比骗子要多，而且当地人知道这里其他的人是骗子还是诚实的人。
你来到这里，要求找出所有的骗子，你可以问这里任何的人A关于另外个人B的问题“B是不是骗子？”。设计一个找出所有骗子的算法，但是时间复杂度是O(n)

------解决方案--------------------
写了一个，最坏时间复杂度O(3n)

import java.util.ArrayList;

import java.util.Collections;

import java.util.Random;



/**

 * 一个地方有两种人：诚实的人和骗子，诚实的人只说真话，骗子可能说真话也可能说假话，已知的是这里诚实的人比骗子要多，

 * 而且当地人知道这里其他的人是骗子还是诚实的人。

 * 你来到这里，要求找出所有的骗子，你可以问这里任何的人A关于另外个人B的问题“B是不是骗子？”。设计一个找出所有骗子的算法，但是时间复杂度是O(n)

 * 

 * 

 */

public class Test008 {



	public static void main(String[] args) {

		ArrayList<People> list = new ArrayList<People>();

		// init

		final int PEOPLE_COUNT = 20;

		final int SWINDLER_COUNT = Math.max(1,

				new Random().nextInt(PEOPLE_COUNT - 1) / 2);

		for (int i = 0; i < SWINDLER_COUNT; ++i) {

			list.add(new Swindler());

		}

		for (int i = 0; i < PEOPLE_COUNT - SWINDLER_COUNT; ++i) {

			list.add(new Honester());

		}

		//打乱顺序

		Collections.shuffle(list);

		//为方便查看结果，显示序号

		for(int i = 0;i < list.size();++i) {

			People p = list.get(i);

			p.setNum(i);

		}

		System.out.println("询问前");

		System.out.println(list);

		//获取骗子序号

		ArrayList<Integer> resultList = findSwindlers(list);

		System.out.println("询问后，骗子序号:");

		System.out.println(resultList);

	}



	/**

	 * 找到一个诚实的人就OK

	 * 第一次询问序号0 ～ N-1，检测第一个人是否是骗子(说他是骗子的人数 >= N/2)

	 * 如果不是骗子，就可以得到结果

	 * 否则从N/2 ~ N-1开始询问，检测第N/2个人是否是骗子(说他是骗子的人数 >= N/4)

	 * ...

	 * 以此类推,直到找出诚实的人

	 * 以上询问时间为N + N/2 + N/4 + N/8 + ... 无限接近O(2n)

	 * 最后询问诚实的人时间复杂度为O(n)

	 * 故总时间复杂度为O(3n)

	 */

	static ArrayList<Integer> findSwindlers(ArrayList<People> list) {

		boolean isHonester = false;

		int start = 0;

		int end = list.size();

		while(!isHonester) {

			int swindlerCount = 0;

			People checkPeople = list.get(start);

			for(int i = start;i < end;++i) {

				People p = list.get(i);

				if(p.say(checkPeople)) {

					++swindlerCount;

				}

			}

			if(swindlerCount >= (end - start) / 2) {

				//骗子

				start = (end + start) / 2;

			} else {

				isHonester = true;

			}

		}

		People honester = list.get(start);

		ArrayList<Integer> resultList = new ArrayList<Integer>();

		for(int i = 0;i < list.size();++i) {

			People p = list.get(i);

			if(honester.say(p)) {

				resultList.add(i);

			}

		}

		return resultList;

	}

}



abstract class People {

	protected boolean isSwindler = false;

	protected int num;//编号

	

	protected void setNum(int num) {

		this.num = num;

	}

	

	protected abstract boolean say(People p);

}



class Honester extends People {

	public Honester() {

		isSwindler = false;

	}



	@Override

	protected boolean say(People p) {

		return p.isSwindler;

	}



	@Override

	public String toString() {

		return num + "诚实";

	}

}



class Swindler extends People {

	public Swindler() {

		isSwindler = true;

	}



	@Override

	protected boolean say(People p) {

		int seed = new Random().nextInt(2);

		return seed == 0;

	}



	@Override

	public String toString() {

		return num + "骗子";

	}

}

------解决方案--------------------
我居然把它做完了，离职了所以闲的蛋疼，数学不好，不要让我求算法复杂度！

package test;



import java.security.SecureRandom;

import java.util.ArrayList;



public class TrustAndLie{

  private static SecureRandom sr=new SecureRandom();



  public static void main(String...args){

    Group unknown=Group.generateSource();

    Group lieGroup=findLieGroup(unknown);

    unknown.removeAll(lieGroup);