第7节 加强堆

最大线段重合问题（用堆的实现）

给定很多线段，每个线段都有两个数[start, end]， 表示线段开始位置和结束位置，左右都是闭区间 规定： 1）线段的开始和结束位置一定都是整数值 2）线段重合区域的长度必须>=1 返回线段最多重合区域中，包含了几条线段

思路：

不优化的方法：

1、遍历每个线段取出线段开始的最小值min与结束的最大值max

2、遍历从min到max上取p=min+0.5再遍历每个线段lines[i][0] < p && lines[i][1] > p若在这个范围则加1，最终算出最大线段重合

优化的方法使用堆实现：

1、将每个线段以开始值start排序

2、定义ans=0，遍历每个线段，若小根堆(PriorityQueue<Integer>)的数据小于等于开始值start依次弹出，然后将结束值end放入小根堆，获取小根堆的size则是该线段目前为止的重合数量cur，ans=max(ans,cur)最终算出最大线段重合

代码：

package class07;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 	最大线段重合问题
 * @author yangyanchao
 *
 */
public class Test01_CoverMax {
	/**
	 * 	不优化的版本
	 * @return
	 */
	public static int maxCoverNoOptimization(int[][] lines) {
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for(int i = 0; i < lines.length; i++) {
			// 获取开始值的最小值
			min = Math.min(min, lines[i][0]);
			// 获取结束值的最大值
			max = Math.max(max, lines[i][1]);
		}
		int ans = 0;
		for(double p = min + 0.5; p < max; p += 1) {
			int pCount = 0;
			for(int i = 0; i < lines.length; i++) {
				if(p > lines[i][0] && p < lines[i][1]) {
					pCount++;
				}
			}
			ans = Math.max(ans, pCount);
		}
		return ans;
	}
	
	/**
	 * 	优化的版本
	 * 	使用小根堆
	 * @return
	 */
	public static int maxCoverOptimization(int[][] lines) {
		Line[] lineList = new Line[lines.length];
		for(int i = 0; i < lineList.length; i++) {
			lineList[i] = new Line(lines[i][0], lines[i][1]);
		}
		// 以start排序
		Arrays.sort(lineList, new StartComparator());
		PriorityQueue<Integer> heap = new PriorityQueue<>();
		int ans = 0;
		for(int i = 0; i < lineList.length; i++) {
			// 如果堆不为空并且堆顶<=线段开始值弹出
			while(!heap.isEmpty() && heap.peek() <= lineList[i].start) {
				heap.poll();
			}
			heap.add(lineList[i].end);
			ans = Math.max(ans, heap.size());
		}
		return ans;
	}
	
	/**
	 * 	线段对象
	 * @author yangyanchao
	 *
	 */
	public static class Line {
		public int start;
		public int end;
		public Line(int start, int end) {
			this.start = start;
			this.end = end;
		}
	}
	
	public static class StartComparator implements Comparator<Line>{
		@Override
		public int compare(Line o1, Line o2) {
			return o1.start - o2.start;
		}
	}
	public static class EndComparator implements Comparator<Line> {

		@Override
		public int compare(Line o1, Line o2) {
			return o1.end - o2.end;
		}
	}
	
	// for test
	public static int[][] generateLines(int N, int L, int R) {
		int size = (int) (Math.random() * N) + 1;
		int[][] ans = new int[size][2];
		for (int i = 0; i < size; i++) {
			int a = L + (int) (Math.random() * (R - L + 1));
			int b = L + (int) (Math.random() * (R - L + 1));
			if (a == b) {
				b = a + 1;
			}
			ans[i][0] = Math.min(a, b);
			ans[i][1] = Math.max(a, b);
		}
		return ans;
	}

	public static void main(String[] args) {

		Line l1 = new Line(4, 9);
		Line l2 = new Line(1, 4);
		Line l3 = new Line(7, 15);
		Line l4 = new Line(2, 4);
		Line l5 = new Line(4, 6);
		Line l6 = new Line(3, 7);

		// 底层堆结构，heap
		PriorityQueue<Line> heap = new PriorityQueue<>(new StartComparator());
		heap.add(l1);
		heap.add(l2);
		heap.add(l3);
		heap.add(l4);
		heap.add(l5);
		heap.add(l6);

		while (!heap.isEmpty()) {
			Line cur = heap.poll();
			System.out.println(cur.start + "," + cur.end);
		}

		System.out.println("test begin");
		int N = 100;
		int L = 0;
		int R = 200;
		int testTimes = 200000;
		for (int i = 0; i < testTimes; i++) {
			int[][] lines = generateLines(N, L, R);
			int ans1 = maxCoverNoOptimization(lines);
			int ans2 = maxCoverOptimization(lines);
			if (ans1 != ans2) {
				System.out.println("ooVoo");
			}
		}
		System.out.println("test end");
	}
}

手动改写堆（非常重要）！

系统提供的堆无法做到的事情： 1）已经入堆的元素，如果参与排序的指标方法变化， 系统提供的堆无法做到时间复杂度O(logN)调整！都是O(N)的调整！ 2）系统提供的堆只能弹出堆顶，做不到自由删除任何一个堆中的元素， 或者说，无法在时间复杂度O(logN)内完成！一定会高于O(logN) 根本原因：无反向索引表

手动改写堆的代码讲解

1）建立反向索引表 2）建立比较器 3）核心在于各种结构相互配合，非常容易出错

代码：

实现加强堆PowerHeap<T>

主要成员

• private ArrayList<T> heap; 动态数组实现完全二叉树结构
• private HashMap<T, Integer> indexMap; 反向索引表
• private int heapSize; 堆的size
• private Comparator<? super T> comp; 比较器

主要方法

• public boolean isEmpty() 是否空
• public int size() 获取堆的size
• public boolean contains(T obj) 判断该对象是否存在
• public T peek() 获取堆顶数据 不弹出
• public void add(T obj) 添加数据
• public T poll() 弹出数据
• public void remove(T obj) 删除数据
• public void resign(T obj) 更新数据
• public List<T> getAllElements() 返回堆上所有元素
• private void heapInsert(int index) index与父节点比对 往上浮
• private void heapify(int index) index与较大的孩子节点比对 往下沉
• private void swap(int i, int j) 交换并更新反向索引表

package class07;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * 	加强堆
 * @author yangyanchao
 * T一定要是非基础类型，有基础类型需求包一层
 * @param <T>
 */
public class PowerHeap<T> {
	/**
	 *	 动态数组实现完全二叉树结构
	 *	父节点位置为(index-1)/2
	 *	左孩子位置为2*index+1
	 *	右孩子位置为2*index+2
	 */
	private ArrayList<T> heap;
	
	/**
	 *	反向索引表
	 *	记录对象在heap的位置
	 */
	private HashMap<T, Integer> indexMap;
	
	/**
	 * 	堆size
	 */
	private int heapSize;
	
	/**
	 * 	比较器
	 */
	private Comparator<? super T> comparator;
	
	public PowerHeap(Comparator<T> comparator) {
		this.heap = new ArrayList<>();
		this.indexMap = new HashMap<>();
		this.heapSize = 0;
		this.comparator = comparator;
	}
	
	/**
	 * 	是否空
	 * @return
	 */
	public boolean isEmpty() {
		return heapSize == 0;
	}
	
	/**
	 * 	获取堆的size
	 * @return
	 */
	public int size() {
		return heapSize;
	}
	
	/**
	 * 	判断该对象是否存在
	 * @param obj
	 * @return
	 */
	public boolean contains(T obj) {
		return indexMap.containsKey(obj);
	}
	
	/**
	 * 	获取堆顶数据 不弹出
	 * @return
	 */
	public T peek() {
		return heap.get(0);
	}
	
	/**
	 * 	添加数据
	 * @param obj
	 */
	public void add(T obj) {
		heap.add(obj);
		indexMap.put(obj, heapSize);
		heapInsert(heapSize++);
	}
	
	/**
	 * 	弹出数据
	 * @return
	 */
	public T poll() {
		T ans = this.peek();
		// 使用自己的删除方法
		this.remove(ans);
//		this.swap(0, heapSize - 1);
//		indexMap.remove(ans);
//		heap.remove(--heapSize);
//		heapify(0);
		return ans;
	}
	
	/**
	 * 	删除数据
	 * @param obj
	 */
	public void remove(T obj) {
		T replace = heap.get(heapSize - 1);
		indexMap.remove(obj);
		heap.remove(--heapSize);
		if(replace != obj) {
			int index = indexMap.get(obj);
			// 说明删除的obj不是最后一个堆数据 执行更换
			heap.set(index, replace);
			indexMap.put(replace, index);
			resign(replace);
		}
	}
	
	/**
	 * 	更新数据
	 * @param obj
	 */
	public void resign(T obj) {
		heapInsert(indexMap.get(obj));
		heapify(indexMap.get(obj));
	}
	
	/**
	 * 	返回堆上所有元素 
	 * @return
	 */
	public List<T> getAllElements() {
		List<T> ans = new ArrayList<>();
		for (T c : heap) {
			ans.add(c);
		}
		return ans;
	}
	
	/**
	 * 	index与父节点比对 往上浮
	 * @param index
	 */
	private void heapInsert(int index) {
		while(comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
			this.swap(index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}
	
	/**
	 * 	index与较大的孩子节点比对 往下沉
	 * @param index
	 */
	private void heapify(int index) {
		int left = 2 * index + 1;
		while(left < this.size()) {
			int largest = left + 1 < this.size() && comparator.compare(heap.get(left + 1), heap.get(left)) < 0 ? left + 1 : left;
			largest = comparator.compare(heap.get(largest), heap.get(index)) < 0 ? largest : index;
			if(index == largest) {
				// index与较大的孩子没有干掉
				break;
			}
			this.swap(largest, index);
			index = largest;
			left = 2 * index + 1;
		}
	}
	
	/**
	 * 	交换并更新反向索引表
	 * @param i
	 * @param j
	 */
	private void swap(int i, int j) {
		T ansi = heap.get(i);
		T ansj = heap.get(j);
		heap.set(i, ansj);
		heap.set(j, ansi);
		indexMap.put(ansj, i);
		indexMap.put(ansi, j);
	}
}

手动改写堆题目练习

给定一个整型数组，int[] arr；和一个布尔类型数组，boolean[] op 两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作 arr = [ 3 , 3 , 1 , 2, 1, 2, 5… op = [ T , T, T, T, F, T, F… 依次表示：3用户购买了一件商品，3用户购买了一件商品，1用户购买了一件商品，2用户购买了一件商品，1用户退货了一件商品，2用户购买了一件商品，5用户退货了一件商品…

一对arr[i]和op[i]就代表一个事件： 用户号为arr[i]，op[i] == T就代表这个用户购买了一件商品 op[i] == F就代表这个用户退货了一件商品 现在你作为电商平台负责人，你想在每一个事件到来的时候， 都给购买次数最多的前K名用户颁奖。 所以每个事件发生后，你都需要一个得奖名单（得奖区）。

得奖系统的规则： 1，如果某个用户购买商品数为0，但是又发生了退货事件， 则认为该事件无效，得奖名单和上一个事件发生后一致，例子中的5用户 2，某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1 3，每次都是最多K个用户得奖，K也为传入的参数 如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果

4，得奖系统分为得奖区和候选区，任何用户只要购买数>0， 一定在这两个区域中的一个 5，购买数最大的前K名用户进入得奖区， 在最初时如果得奖区没有到达K个用户，那么新来的用户直接进入得奖区 6，如果购买数不足以进入得奖区的用户，进入候选区

7，如果候选区购买数最多的用户，已经足以进入得奖区， 该用户就会替换得奖区中购买数最少的用户（大于才能替换）， 如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户 如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户

8，候选区和得奖区是两套时间， 因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有 从得奖区出来进入候选区的用户，得奖区时间删除， 进入候选区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i） 从候选区出来进入得奖区的用户，候选区时间删除， 进入得奖区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）

9，如果某用户购买数==0，不管在哪个区域都离开，区域时间删除， 离开是指彻底离开，哪个区域也不会找到该用户 如果下次该用户又发生购买行为，产生>0的购买数， 会再次根据之前规则回到某个区域中，进入区域的时间重记

请遍历arr数组和op数组，遍历每一步输出一个得奖名单

public List<List<Integer>> topK (int[] arr, boolean[] op, int k)

代码实现有暴力不优化版本至少是O(N^2*logN)，也有使用手写的加强堆版本O(N*(logN+logk+k))

这一题集中体现了算法的魅力，在解决业务场景下游刃有余。

思路：

不优化版本：

1、新建Customer类，属性public int id;public int buy;public int enterTime;

2、定义map记录id与Customer映射关系，获奖名单ArrayList<Customer> daddys

​ 候选名单ArrayList<Customer> cands 每步事件产出的topK名单List<List<Integer>> ans

3、遍历arr对事件做出判断

优化版本使用加强堆实现：

package class07;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * 	得奖系统问题
 * @author yangyanchao
 *
 */
public class Test02_EveryStepShowBoss {
	
	/**
	 * 	客户类
	 * @author yangyanchao
	 *
	 */
	public static class Customer {
		public int id;
		public int buy;
		public int enterTime;
		public Customer(int id, int buy, int enterTime) {
			this.id = id;
			this.buy = buy;
			this.enterTime = enterTime;
		}
	}
	
	/**
	 * 	不优化版本
	 * 	返回每个事件的前k名得奖名单
	 * @param arr
	 * @param op
	 * @param k
	 * @return
	 */
	public static List<List<Integer>> topKNoOptimization(int[] arr, boolean[] op, int k) {
		// 记录id与客户关系映射关系
		HashMap<Integer, Customer> map = new HashMap<>();
		// 记录候选名单list
		ArrayList<Customer> cands = new ArrayList<Customer>();
		// 记录得奖名单list
		ArrayList<Customer> daddys = new ArrayList<Customer>();
		List<List<Integer>> ans = new ArrayList<List<Integer>>();
		// 遍历事件
		for(int i = 0; i < arr.length; i++) {
			// 客户id
			int id = arr[i];
			// 客户的操作
			boolean buyOrReturn = op[i];
			if(!buyOrReturn && !map.containsKey(id)) {
				// 客户发生了退货而且map中还不存在 则认为该事件无效，得奖名单和上一个事件发生后一致
				ans.add(getDaddys(daddys));
				continue;
			}
			
			if(!map.containsKey(id)) {
				// 要么是新客户
				// 要么是之前的客户但是购买数量为0则剔除了
				map.put(id, new Customer(id, 0, 0));
			}
			Customer customer = map.get(id);
			if(buyOrReturn) {
				customer.buy++;
			} else {
				customer.buy--;
			}
			if(customer.buy == 0) {
				map.remove(id);
				// 后续逻辑中会将候选区与得奖区的名单删除buy==0的
			} 
			if (!cands.contains(customer) && !daddys.contains(customer)) {
				// 判断入哪个区域
				if(daddys.size() < k) {
					// 如果得奖区size<k则customer入得奖区
					customer.enterTime = i;
					daddys.add(customer);
				} else {
					// 反之，入候选区
					customer.enterTime = i;
					cands.add(customer);
				}
			}
			// 将候选区的名单删除buy==0的
			clearZeroBuy(cands);
			// 将得奖区的名单删除buy==0的
			clearZeroBuy(daddys);
			// 得奖区域名单排序 按照buy升序(购买数最少的) buy相等得情况下 enterTime升序(最早进入)
			daddys.sort(new DaddysComparator());
			// 候选区域名单排序 按照buy降序(购买数最多的) buy相等得情况下 enterTime升序(最早进入)
			cands.sort(new CandsComparator());
			// 比对及移动区域数据
			move(daddys, cands, i, k);
			ans.add(getDaddys(daddys));
		}
		return ans;
	}

	/**
	 * 	通过得奖名单获取得奖ids
	 * @param daddys
	 * @return
	 */
	private static List<Integer> getDaddys(ArrayList<Customer> daddys) {
		List<Integer> ids = new ArrayList<>();
		for(Customer c : daddys) {
			ids.add(c.id);
		}
		return ids;
	}

	/**
	 * 	比对及移动区域数据
	 * @param daddys
	 * @param cands
	 * @param time
	 * @param k
	 */
	private static void move(ArrayList<Customer> daddys, ArrayList<Customer> cands,
			int time, int k) {
		if(cands.isEmpty()) {
			// 获选区都没有 不用比对了
			return;
		}
		if(daddys.size() < k) {
			Customer c = cands.get(0);
			c.enterTime = time;
			daddys.add(c);
			cands.remove(0);
		} else if(cands.get(0).buy > daddys.get(0).buy) {
			// 得奖区满了
			Customer oldDaddy = daddys.get(0);
			daddys.remove(0);
			Customer newDaddy = cands.get(0);
			cands.remove(0);
			newDaddy.enterTime = time;
			oldDaddy.enterTime = time;
			daddys.add(newDaddy);
			cands.add(oldDaddy);
		}
	}
	
	/**
	 * 	得奖区域名单排序
	 * @author yangyanchao
	 *
	 */
	private static class DaddysComparator implements Comparator<Customer> {
		@Override
		public int compare(Customer o1, Customer o2) {
			return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
		}
	}
	
	/**
	 * 	候选区域名单排序
	 * @author yangyanchao
	 *
	 */
	private static class CandsComparator implements Comparator<Customer> {
		@Override
		public int compare(Customer o1, Customer o2) {
			return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
		}
	}

	/**
	 * 	删除该区域中buy==0的
	 * @param cands
	 */
	private static void clearZeroBuy(ArrayList<Customer> arr) {
		List<Customer> noZero = new ArrayList<Customer>();
		for (Customer c : arr) {
			if (c.buy != 0) {
				noZero.add(c);
			}
		}
		arr.clear();
		for (Customer c : noZero) {
			arr.add(c);
		}
	}
	
	/**
	 * 	优化版本 使用加强堆
	 * 	返回每个事件的前k名得奖名单
	 * @param arr
	 * @param op
	 * @param k
	 * @return
	 */
	public static List<List<Integer>> topKOptimization(int[] arr, boolean[] op, int k) {
		List<List<Integer>> ans = new ArrayList<List<Integer>>();
		WhosYourDaddys wyd = new WhosYourDaddys(k);
		for(int i = 0; i < arr.length; i++) {
			// 对事件进行操作
			wyd.operation(arr[i], op[i], i);
			// 获取得奖名单
			ans.add(wyd.getDaddysIds());
		}
		return ans;
	}
	
	/**
	 * 	通过事件获取前k名得奖名单
	 * @author yangyanchao
	 *
	 */
	public static class WhosYourDaddys {
		/**
		 * 	候选名单
		 */
		private PowerHeap<Customer> cands;
		/**
		 * 	得奖名单
		 */
		private PowerHeap<Customer> daddys;
		
		/**
		 * 	id与客户对象的映射表
		 */
		private HashMap<Integer, Customer> map;
		
		/**
		 * 	得奖名单长度k
		 */
		private final int daddyLimit;
		
		public WhosYourDaddys(int daddyLimit) {
			this.cands = new PowerHeap<Customer>(new CandsComparator());
			this.daddys = new PowerHeap<Customer>(new DaddysComparator());
			this.map = new HashMap<Integer, Customer>();
			this.daddyLimit = daddyLimit;
		}

		/**
		 * 	获取得奖名单
		 * @return
		 */
		public List<Integer> getDaddysIds() {
			List<Integer> ans = new ArrayList<Integer>();
			List<Customer> list = this.daddys.getAllElements();
			for(Customer c : list) {
				ans.add(c.id);
			}
			return ans;
		}

		/**
		 * 	对事件进行操作
		 * @param id
		 * @param buyOrReturn
		 * @param time
		 * @param k
		 */
		public void operation(int id, boolean buyOrReturn, int time) {
			if(!buyOrReturn && !map.containsKey(id)) {
				// 客户发生退货并且客户map中不存在该客户则认为该事件无效，得奖名单和上一个事件发生后一致
				return;
			}
			if(!map.containsKey(id)) {
				// 要么是新客户
				// 要么是客户buy==0被剔除了
				map.put(id, new Customer(id, 0, 0));
			}
			Customer customer = map.get(id);
			if(buyOrReturn) {
				// 买
				customer.buy++;
			} else {
				// 退
				customer.buy--;
			}
			if(customer.buy == 0) {
				// 购买数为0 剔除
				map.remove(id);
			}
			if(!cands.contains(customer) && !daddys.contains(customer)) {
				// 若该客户既不在候选名单也不在得奖名单
				// 判断得奖区域是否<k
				if(daddys.size() < daddyLimit) {
					// 得奖区域不满
					customer.enterTime = time;
					daddys.add(customer);
				} else {
					customer.enterTime = time;
					cands.add(customer);
				}
			} else if(cands.contains(customer)) {
				// 若该客户在候选名单
				if(customer.buy == 0) {
					cands.remove(customer);
				} else {
					cands.resign(customer);
				}
			} else if(daddys.contains(customer)) {
				// 若该客户在得奖名单
				if(customer.buy == 0) {
					daddys.remove(customer);
				} else {
					daddys.resign(customer);
				}
			}
			// 候选区域与得奖区域比对
			candsMoveDaddys(time);
		}

		/**
		 * 	候选区域与得奖区域比对
		 * @param time
		 */
		private void candsMoveDaddys(int time) {
			if(cands.isEmpty()) {
				// 候选区域为空不参与比对
				return;
			}
			if(daddys.size() < daddyLimit) {
				// 若得奖区域不满
				Customer candsBest = cands.poll();
				candsBest.enterTime = time;
				daddys.add(candsBest);
			} else if(cands.peek().buy > daddys.peek().buy) {
				Customer oldDaddy = daddys.poll();
				Customer newDaddy = cands.poll();
				oldDaddy.enterTime = time;
				newDaddy.enterTime = time;
				daddys.add(newDaddy);
				cands.add(oldDaddy);
			}
		}
	}
	
	// 为了测试
		public static class Data {
			public int[] arr;
			public boolean[] op;

			public Data(int[] a, boolean[] o) {
				arr = a;
				op = o;
			}
		}

		// 为了测试
		public static Data randomData(int maxValue, int maxLen) {
			int len = (int) (Math.random() * maxLen) + 1;
			int[] arr = new int[len];
			boolean[] op = new boolean[len];
			for (int i = 0; i < len; i++) {
				arr[i] = (int) (Math.random() * maxValue);
				op[i] = Math.random() < 0.5 ? true : false;
			}
			return new Data(arr, op);
		}

		// 为了测试
		public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
			if (ans1.size() != ans2.size()) {
				return false;
			}
			for (int i = 0; i < ans1.size(); i++) {
				List<Integer> cur1 = ans1.get(i);
				List<Integer> cur2 = ans2.get(i);
				if (cur1.size() != cur2.size()) {
					return false;
				}
				cur1.sort((a, b) -> a - b);
				cur2.sort((a, b) -> a - b);
				for (int j = 0; j < cur1.size(); j++) {
					if (!cur1.get(j).equals(cur2.get(j))) {
						return false;
					}
				}
			}
			return true;
		}

		public static void main(String[] args) {
			int maxValue = 10;
			int maxLen = 100;
			int maxK = 6;
			int testTimes = 100000;
			System.out.println("测试开始");
			for (int i = 0; i < testTimes; i++) {
				Data testData = randomData(maxValue, maxLen);
				int k = (int) (Math.random() * maxK) + 1;
				int[] arr = testData.arr;
				boolean[] op = testData.op;
				List<List<Integer>> ans1 = topKOptimization(arr, op, k);
				List<List<Integer>> ans2 = topKNoOptimization(arr, op, k);
				if (!sameAnswer(ans1, ans2)) {
					for (int j = 0; j < arr.length; j++) {
						System.out.println(arr[j] + " , " + op[j]);
					}
					System.out.println(k);
					System.out.println(ans1);
					System.out.println(ans2);
					System.out.println("出错了！");
					break;
				}
			}
			System.out.println("测试结束");
		}
}