执行结果:通过
执行用时和内存消耗如下：
代码如下：
#define FATHER_NODE(i) (0 == (i) ? -1 : (i) - 1 >> 1)
#define LEFT_NODE(i) (((i) << 1) + 1)
#define RIGHT_NODE(i) (((i) << 1) + 2)
#define HIGH_INT(i) ((i) >> 32)
#define LOW_INT(i) ((i) & 0xFFFFFFFF)
#define MERGE_LONG(i, j) ((long long)(i) << 32 | (long long)(j))
#define MAX_VAL(i, j) ((i) > (j) ? (i) : (j))
#define MIN_VAL(i, j) ((i) < (j) ? (i) : (j))
/* 优先队列（大根堆）。 */
typedef struct
{
long long *arr;
int arrSize;
}
PriorityQueue;
/* 二进制树。 */
typedef struct
{
int *arr;
int highestBit;
}
BinaryTree;
static void queuePush(PriorityQueue *queue, long long value);
static void queuePop(PriorityQueue *queue);
static int mapSearchSmallerEqual(int *arr, int arrSize, int value);
static int mapSearchBiggerEqual(int *arr, int arrSize, int value);
static int treeHighestBit(int value);
static void treePush(BinaryTree *tree, int value);
static int treeSmallerEqual(BinaryTree *tree, int value);
static int treeBiggerEqual(BinaryTree *tree, int value);
/* 主函数。 */
int *closestRoom(int **rooms, int roomsSize, int *roomsColSize, int **queries, int queriesSize, int *queriesColSize, int *returnSize)
{
const int treeSize = roomsSize * 3;
int i = 0, j = INT_MAX, k = 0, idMapSize = 0, minId = INT_MAX, maxId = INT_MIN;
int arr1[treeSize], idMap[roomsSize];
long long arr2[roomsSize], arr3[queriesSize];
BinaryTree tree;
PriorityQueue rQueue, qQueue;
int *result = NULL;
/* 初始化。 */
memset(arr1, 0, sizeof(arr1));
tree.arr = arr1;
tree.highestBit = treeHighestBit(roomsSize - 1);
rQueue.arr = arr2;
rQueue.arrSize = 0;
qQueue.arr = arr3;
qQueue.arrSize = 0;
result = (int *)malloc(sizeof(int) * queriesSize);
if(NULL == result)
{
*returnSize = 0;
return result;
}
/* 对rooms数组中所有的ID进行离散化。注意由于是借用的大根堆处理离散化，所以取相反数以达到结果从小到大取值的效果。 */
for(i = 0; roomsSize > i; i++)
{
queuePush(&rQueue, -rooms[i][0]);
}
while(0 < rQueue.arrSize)
{
/* 这里j初始化为最大值，以表示上一个idMap值，以此保证idMap里面的数值无重复。注意idMap取相反数。 */
if(j > rQueue.arr[0])
{
j = rQueue.arr[0];
idMap[idMapSize] = -j;
idMapSize++;
}
queuePop(&rQueue);
}
/* 然后把rooms数组的id、size组合，queries数组的minSize、下标组合，放入各自的大根堆。 */
for(i = 0; roomsSize > i; i++)
{
queuePush(&rQueue, MERGE_LONG(rooms[i][1], rooms[i][0]));
}
for(i = 0; queriesSize > i; i++)
{
queuePush(&qQueue, MERGE_LONG(queries[i][1], i));
}
/* 然后给queries的堆进行逐个出堆检查。 */
while(0 < qQueue.arrSize)
{
/* 取出当前要处理的queries的下标。 */
i = LOW_INT(qQueue.arr[0]);
/* 把所有当前面积大于等于queries[i].minSize的房间出堆。 */
while(0 < rQueue.arrSize && queries[i][1] <= HIGH_INT(rQueue.arr[0]))
{
k = LOW_INT(rQueue.arr[0]);
/* 这里存入树中的id，只存映射的离散值。同时更新最大id与最小id。 */
j = mapSearchSmallerEqual(idMap, idMapSize, k);
treePush(&tree, j);
maxId = MAX_VAL(maxId, k);
minId = MIN_VAL(minId, k);
/* 出堆。 */
queuePop(&rQueue);
}
/* 处理当前这一次查询的结果。如果当前的rQueue仍然满员，说明没有任何满足条件的房间被释放出来。 */
if(roomsSize == rQueue.arrSize)
{
result[i] = -1;
}
/* 如果已有的最大id都小于等于当前preferId，则说明只能取这个最大id。 */
else if(maxId <= queries[i][0])
{
result[i] = maxId;
}
/* 如果已有的最小id都大于等于当前preferId，则说明只能取这个最小id。 */
else if(minId >= queries[i][0])
{
result[i] = minId;
}
/* 除上面几种情况以外，接下来都存在左右两个id，此时取较近的，如果两者一样近，取左边的。 */
else
{
/* 由于是离散化处理的，所以这个preferId也先找小于等于自己的最接近的离散化值。 */
j = mapSearchSmallerEqual(idMap, idMapSize, queries[i][0]);
j = treeSmallerEqual(&tree, j);
/* 同上，查找大于等于自己的数值时，也先离散化。 */
k = mapSearchBiggerEqual(idMap, idMapSize, queries[i][0]);
k = treeBiggerEqual(&tree, k);
result[i] = (idMap[k] - queries[i][0] < queries[i][0] - idMap[j]) ? idMap[k] : idMap[j];
}
/* 出堆。 */
queuePop(&qQueue);
}
/* 结果数组的长度等于queriesSize。 */
*returnSize = queriesSize;
return result;
}
/* 大根堆入队。 */
static void queuePush(PriorityQueue *queue, long long value)
{
int son = queue->arrSize, father = FATHER_NODE(son);
queue->arrSize++;
while(-1 != father && value > queue->arr[father])
{
queue->arr[son] = queue->arr[father];
son = father;
father = FATHER_NODE(son);
}
queue->arr[son] = value;
return;
}
/* 大根堆出队。 */
static void queuePop(PriorityQueue *queue)
{
int father = 0, left = LEFT_NODE(father), right = RIGHT_NODE(father), son = 0;
queue->arrSize--;
while((queue->arrSize > left && queue->arr[queue->arrSize] < queue->arr[left])
|| (queue->arrSize > right && queue->arr[queue->arrSize] < queue->arr[right]))
{
son = (queue->arrSize > right && queue->arr[left] < queue->arr[right]) ? right : left;
queue->arr[father] = queue->arr[son];
father = son;
left = LEFT_NODE(father);
right = RIGHT_NODE(father);
}
queue->arr[father] = queue->arr[queue->arrSize];
return;
}
/* 在一个由小到大且无重复的数组中，查找小于等于value的最大位置。题目保证能找到。 */
static int mapSearchSmallerEqual(int *arr, int arrSize, int value)
{
int mid = 0, left = 0, right = arrSize - 1;
while(left < right)
{
mid = left + right + 1 >> 1;
if(value < arr[mid])
{
right = mid - 1;
}
else
{
left = mid;
}
}
return left;
}
/* 在一个由小到大且无重复的数组中，查找大于等于value的最小位置。题目保证能找到。 */
static int mapSearchBiggerEqual(int *arr, int arrSize, int value)
{
int mid = 0, left = 0, right = arrSize - 1;
while(left < right)
{
mid = left + right >> 1;
if(value > arr[mid])
{
left = mid + 1;
}
else
{
right = mid;
}
}
return right;
}
/* 在二进制树中，可能出现的最大值需要占据的最高比特。如果是0，则标记为1。 */
static int treeHighestBit(int value)
{
int result = 1;
if(0 != value)
{
while(0 != value)
{
result++;
value = value >> 1;
}
result = 1 << result - 2;
}
return result;
}
/* 将一个数值放到二进制树中。 */
static void treePush(BinaryTree *tree, int value)
{
int i = 0, bit = tree->highestBit;
while(0 != bit)
{
i = (bit & value) ? RIGHT_NODE(i) : LEFT_NODE(i);
tree->arr[i]++;
bit = bit >> 1;
}
return;
}
/* 查找树中小于等于value的最大值。题目保证其存在。 */
static int treeSmallerEqual(BinaryTree *tree, int value)
{
int i = 0, bit = tree->highestBit, ri = -1, rbit = -1, result = 0;
while(0 != bit)
{
if(bit & value)
{
if(0 != tree->arr[LEFT_NODE(i)])
{
ri = LEFT_NODE(i);
rbit = bit;
}
i = RIGHT_NODE(i);
}
else
{
i = LEFT_NODE(i);
}
bit = bit >> 1;
}
/* 如果该数值本身存在于树中，则就是它本身。 */
if(0 != tree->arr[i])
{
result = value;
}
/* 否则从最后一次分支的地方开始尽量找最大值。 */
else
{
result = value & ~(rbit | rbit - 1);
rbit = rbit >> 1;
while(0 != rbit)
{
if(0 != tree->arr[RIGHT_NODE(ri)])
{
result |= rbit;
ri = RIGHT_NODE(ri);
}
else
{
ri = LEFT_NODE(ri);
}
rbit = rbit >> 1;
}
}
return result;
}
/* 查找树中大于等于value的最小值。题目保证其存在。 */
static int treeBiggerEqual(BinaryTree *tree, int value)
{
int i = 0, bit = tree->highestBit, ri = -1, rbit = -1, result = 0;
while(0 != bit)
{
if(bit & value)
{
i = RIGHT_NODE(i);
}
else
{
if(0 != tree->arr[RIGHT_NODE(i)])
{
ri = RIGHT_NODE(i);
rbit = bit;
}
i = LEFT_NODE(i);
}
bit = bit >> 1;
}
/* 如果该数值本身存在于树中，则就是它本身。 */
if(0 != tree->arr[i])
{
result = value;
}
/* 否则从最后一次分支的地方开始尽量找最小值。 */
else
{
result = value & ~(rbit - 1) | rbit;
rbit = rbit >> 1;
while(0 != rbit)
{
if(0 != tree->arr[LEFT_NODE(ri)])
{
ri = LEFT_NODE(ri);
}
else
{
result |= rbit;
ri = RIGHT_NODE(ri);
}
rbit = rbit >> 1;
}
}
return result;
}
解题思路：
离线查询。
1.题目中，对于每一个查询queries[x]，必须在面积大于等于queries[x][1]的房间之中，查找其中ID离自己的ID，即queries[x][0]最接近的。也就是说，所有面积小于queries[x][1]的房间，即便它的ID再怎么靠近queries[x][0]，也是不被考虑的。那么，我们就需要按照面积从大到小的顺序查看每一个queries[x]，然后同样的，从大到小的顺序过滤每一个面积大于等于当前queries[x][1]的房间。
2.这就是离线查询的思路，即，我们计算的实际顺序，和queries[][]数组本身的顺序不一致，是按照queries[x][1]从大到小的顺序计算的，每次遍历到queries[x]的时候，就将面积大于等于queries[x][1]的房间给释放出来。
优先队列（大根堆）。
我们将所有的房间（下标），和查询（下标）都存到各自的优先队列之中，然后，每当从查询优先队列的队顶pop一个查询的时候，就把房间优先队列中，面积大于等于该查询面积的房间pop出来。这样就达到了已经释放出来的所有房间，其面积一定都是大于等于当前的查询面积的。
二进制树（01字典树）。
1.我们将所有已经释放出来的房间的ID，都存放到一个数据结构中，在这个数据结构中，我们需要能够快速地确定，所有的这些ID，哪个离当前查询的ID最接近，如果有左右两侧两个数值都和查询ID一样近，则取左边的那个。
当我们需要往二进制树中存入一个数值的时候（本题中存入的是房间ID），我们从这个数值的最高比特开始，如果最高比特为1，则从根节点往右存储，当右节点为空的时候，新建右节点，如果最高比特为0，则从根节点往左存储，当左节点为空的时候，新建左节点。然后到第二高比特，类似的，如果该比特为1，则从当前节点往右存储，当右节点为空的时候，新建右节点，如果当前比特为0，则从当前节点往左存储，当左节点为空的时候，新建左节点。继续第三高比特，处理逻辑同上，依此类推，直到最低比特结束。下图中，就是我们存入2,4,6,8,9,11,13,14这几个数值之后的示意图。
2.这里，我们只计算了最低4位的比特。题目中ID的取值最大可以到10^7，即最多达到24比特。这里就不展开了，其处理逻辑是一样的。
上面讲了往二进制树中存入数值的处理方法，那么，我们怎么查找这棵树中，小于等于某个数值的最大值，和大于等于某个数值的最小值呢？也就是题目中要求的，最接近queries[x][0]的房间ID。
3.我们先看小于等于某个数值的最大值。还是以这个图为例，假如现在我们要在已经存入树中的2,4,6,8,9,11,13,14这几个数值中，查找小于等于10的最大值，凭我们肉眼查看，这个值应该就是9，那么我们怎么在二叉树中用代码来实现呢？
3.我们可以这样处理，把这个要比较的数值10，从最高位到最低位的顺序往下罗列，二进制是1010(b)，看看从上到下的过程中，最后一次“1010(b)往右分支走的同时左分支不为空的分叉点”在哪里。听起来有点拗口是不是，没关系，我们在图中看，第二高位这一层，我们标记红色字母(a)的这个节点的左节点，就是我们要找的。在节点(a)处，1010(b)要往右，但同时左分支不为空，我们就把这个节点(a)的左分支记录下来。然后，这个左分支开始往下，能靠右尽量靠右找，右分支不存在的情况下再靠左，按照这个逻辑，找到的就是1001(b)，即十进制的9。我这个图里只画了四层，如果有从上到下有好多比特，则记录最下面一次分叉的位置，也就是越晚分叉，其差值越小。
类似的，大于等于某个数值的最大值，其处理逻辑可以参考上面的过程，读者可以自行展开。
4.特别留意一下，上面所述的“大于等于某个数值的最小值”，和“小于等于某个数值的最大值”，都包含了“等于”。也就是说，如果查询的这个数值本身就在二进制树里面，那么就直接返回这个数值本身。
【代码】
时间复杂度，O(R*log(R) + Q*log(Q))。
空间复杂度，O(R+Q)。
其中，R表示房间数组的长度，Q表示查询数组的长度。