给你一个整数数组 instructions ，你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums ，你需要 从左到右 遍历 instructions 中的元素，将它们依次插入 nums 数组中。每一次插入操作的 代价 是以下两者的 较小值 ：
nums 中 严格小于 instructions[i] 的数字数目。 nums 中 严格大于 instructions[i] 的数字数目。
比方说，如果要将 3 插入到 nums = [1,2,3,5] ，那么插入操作的 代价 为 min(2, 1) (元素 1 和 2 小于 3 ，元素 5 大于 3 ），插入后 nums 变成 [1,2,3,3,5] 。
请你返回将 instructions 中所有元素依次插入 nums 后的 总最小代价 。由于答案会很大，请将它对 109 + 7 取余 后返回。
示例 1：
输入：instructions = [1,5,6,2]
输出：1
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 5 ，代价为 min(1, 0) = 0 ，现在 nums = [1,5] 。
插入 6 ，代价为 min(2, 0) = 0 ，现在 nums = [1,5,6] 。
插入 2 ，代价为 min(1, 2) = 1 ，现在 nums = [1,2,5,6] 。
总代价为 0 + 0 + 0 + 1 = 1 。
示例 2:
输入：instructions = [1,2,3,6,5,4]
输出：3
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 2 ，代价为 min(1, 0) = 0 ，现在 nums = [1,2] 。
插入 3 ，代价为 min(2, 0) = 0 ，现在 nums = [1,2,3] 。
插入 6 ，代价为 min(3, 0) = 0 ，现在 nums = [1,2,3,6] 。
插入 5 ，代价为 min(3, 1) = 1 ，现在 nums = [1,2,3,5,6] 。
插入 4 ，代价为 min(3, 2) = 2 ，现在 nums = [1,2,3,4,5,6] 。
总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。
示例 3：
输入：instructions = [1,3,3,3,2,4,2,1,2]
输出：4
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3,3] 。
插入 2 ，代价为 min(1, 3) = 1 ，现在 nums = [1,2,3,3,3] 。
插入 4 ，代价为 min(5, 0) = 0 ，现在 nums = [1,2,3,3,3,4] 。
插入 2 ，代价为 min(1, 4) = 1 ，现在 nums = [1,2,2,3,3,3,4] 。
插入 1 ，代价为 min(0, 6) = 0 ，现在 nums = [1,1,2,2,3,3,3,4] 。
插入 2 ，代价为 min(2, 4) = 2 ，现在 nums = [1,1,2,2,2,3,3,3,4] 。
总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。
int min(int num,int *n,int val){
int i=0;
int sam=0;
for(i;i
if(val
break;
}
}
return i;
}
int createSortedArray(int* instructions, int instructionsSize){
int i;
int sum=0;
int n[instructionsSize];
int j;
int mini;
int max;
int r=0;
int pr;
int rn[instructionsSize];
for(i=0;i
if(i==0){
n[r]=instructions[r];
rn[r++]=1;
}
else{
// index_min=min(i,n,instructions[i]);
mini=0;
max=0;
pr=0;
for(j=0;j
if(instructions[i]==n[j]){
rn[j]++;
pr=1;
}
if(instructions[i]>n[j]){
max=max+rn[j];
}
if(instructions[i]
mini=mini+rn[j];
}
}
if(pr==0){
printf("r %d ",r);
n[r]=instructions[i];
rn[r++]=1;
}
// printf("min %d max %d ",mini,max);
if(max>mini){
sum=sum+mini;
}
else sum=sum+max;
}
}
return sum;
}
当然，上面算法时间复杂度肯定是解决不了的，所以我们再给一个解法
instructions数组中的数值，是从左到右的顺序安插到目标数组中的。所以，当执行到instructions[x]时，前面已有的比自己小，与比自己大的数值，全都在[0, x - 1]之间，与[x + 1, instructionsSize)之间的数值无关。
那么，题目的含义就转变成了：求每一个instructions[x]在数组中，它所在位置的左侧，有多少小于自己的数值，和大于自己的数值，求两者数量的较小值，然后，所有instructions[x]的这个最小值的总和，就是结果。
接下来，题目就和另一题《计算右侧小于当前元素的个数》本质上是一样的了。只不过本题是把右侧改为左侧，并且同时计算小于当前元素和大于当前元素的个数。
即设立一棵二叉树，每个instructions[x]存放入这棵二叉树的原则是：从它的二进制最高位到最低位，依次查看每一位是1还是0，如果是1，则往二叉树右侧走，如果是0，则往二叉树左侧走，记录每个分支往左和往右的次数。同时，每次往二叉树中插入instructions[x]时，都顺便检查一下有多少数值是和自己在当前节点分道扬镳的。比如，当前位是1，那么它往右走的同时，已经在当前节点往左走的数值，肯定都小于自己，计数。当前位是0，那么它往左走的同时，已经在当前节点往右走的数值，肯定都大于自己，计数。当它执行到最后一位时，自己存入了二叉树，同时也将小于自己和大于自己的数值数量给计算出来了。
instructions[x]数值的取值范围是[1, 10^5]，所以最高位是第20位，即，不用遍历整个int类型的32位。
这种解法类似哈夫曼树上进行求解，当然，这个解法是相当棒的
代码如下：
#define MAX_BITS 0x20000
#define MODULE_NUMBER 1000000007
#define MIN_VAL(a, b) (((a) < (b)) ? (a) : (b))
int createSortedArray(int *instructions, int instructionsSize)
{
int x = 0, bits = 0, bigger = 0, smaller = 0, result = 0;
struct TreeNode *root = NULL, *node = NULL;
root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->left = NULL;
root->right = NULL;
while(instructionsSize > x)
{
bigger = 0;
smaller = 0;
node = root;
bits = MAX_BITS;
while(0 != bits)
{
if(instructions[x] & bits)
{
if(NULL != node->left)
{
smaller += node->left->val;
}
if(NULL == node->right)
{
node->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->right->val = 1;
node->right->left = NULL;
node->right->right = NULL;
}
else
{
node->right->val++;
}
node = node->right;
}
else
{
if(NULL != node->right)
{
bigger += node->right->val;
}
if(NULL == node->left)
{
node->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->left->val = 1;
node->left->left = NULL;
node->left->right = NULL;
}
else
{
node->left->val++;
}
node = node->left;
}
bits = bits >> 1;
}
result += MIN_VAL(bigger, smaller);
if(MODULE_NUMBER <= result)
{
result -= MODULE_NUMBER;
}
x++;
}
return result;
}
