题目描述：
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
今日学习：
1.二分法的灵活应用：sorted每次加入一个元素看它应该在哪个位置
2.线段树：这个有点太难了Orz...参考：博客1，博客2
3.复习归并排序
题解：
1.暴力法
2.二分法
3.归并1
4.归并2
5.线段树
6.巧妙的方法
/**
* @param {number[]} nums
* @return {number[]}
*/
//暴力法
var countSmaller = function(nums) {
let len = nums.length
// let res = new Array()
for(let i = 0; i < len; i++) {
let cur = nums[i]
let count = 0
for(let j = i + 1; j < len; j++) {
if(cur > nums[j]) {
count++
}
}
// res.push(count)
nums[i] = count
}
// return res
return nums
};
//二分查找
var countSmaller = function(nums) {
let len = nums.length
if(len == 0) return nums
// let counts = new Array(len)
let sorted = []
for(let i = len - 1; i >= 0; i--) {
let index = findIndex(sorted, nums[i])
sorted.splice(index, 0, nums[i])
// counts[i] = index
nums[i] = index
}
// return counts
return nums
}
var findIndex = function(arr, target) {
let low = 0
let high = arr.length - 1
while(low < high) {
let mid = (low + high) >> 1
if(target > arr[mid]) {
low = mid + 1
}else {
high = mid
}
}
if(arr[low] < target) return low + 1
else return low
}
//归并排序1
function countSmaller(nums) {
if (!nums.length) return []
let objArr = [] //对象和index
let resArr = [] //存放次数
for (let i = 0; i < nums.length; i++) {
const ele = nums[i]
let obj = {
num: ele,
index: i
}
resArr.push(0)
objArr.push(obj)
}
haha(objArr)
return resArr
function haha(nums) {
if (nums.length === 1) return nums
let mid = nums.length >> 1
let left = nums.slice(0, mid)
let right = nums.slice(mid, nums.length)
return merge(haha(left), haha(right))
}
function merge(left, right) {
let res = []
// 定义“后有序数组”中一个指针
let j = 0
while (left.length && right.length) {
if (left[0].num > right[0].num) {
res.push(right[0])
right.shift()
j++
} else {
// “前有序数组” 的元素出列的时候，数一数 “后有序数组” 已经出列了多少元素
resArr[left[0].index] += j
res.push(left[0])
left.shift()
}
}
while (left.length) {
// 同理
resArr[left[0].index] += j
res.push(left[0])
left.shift()
}
while (right.length) {
res.push(right[0])
right.shift()
j++
}
return res
}
}
//归并排序2
var countSmaller = function(nums) {
let len = nums.length;
let arr_index = new Array(len);
nums.forEach((_,key)=>{
arr_index[key] = key;
})
let ans = new Array(len).fill(0);
const merge = (left, right)=>{
let llen = left.length;
let rlen = right.length;
let len = llen+rlen;
let res = new Array(len);
for(let i = 0, j= 0, k= 0 ; k <len;++k){
if(i == llen){
res[k] = right[j++]
}else if(j == rlen){
res[k] = left[i++];
}else if(nums[left[i]]>nums[right[j]]){
ans[left[i]]+=(rlen-j);
res[k] = left[i++];
}else{
res[k] = right[j++];
}
}
return res;
}
const mergeSort = (arr)=>{
if(arr.length<2){
return arr;
}
let len = arr.length;
let mid = len>>1;
let left = arr.slice(0,mid);
let right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
mergeSort(arr_index);
return ans;
};
//线段树
var countSmaller = function(nums) {
if (nums.length === 0) return [];
let min = Infinity,
max = -Infinity,
nlen = nums.length,
segmentTree = [],
c = 0,
ans = [];
// 求最大值和最小值
for (let i = 0; i < nlen; i++) {
if (nums[i] < min) {
min = nums[i];
}
if (nums[i] > max) {
max = nums[i];
}
}
// 使用数组构建线段树 - 递归
function createSegmentTree(start, end, p) {
segmentTree[p] = {
start: start,
end: end,
count: 0
};
if (start === end) return ;
let mid = Math.floor((end - start) / 2) + start;
createSegmentTree(start, mid, 2 * p + 1);
createSegmentTree(mid + 1, end, 2 * p + 2);
}
createSegmentTree(min, max, 0);
// 将当前元素放入线段树中
function setElement(val, p) {
if (segmentTree[p] !== undefined && val >= segmentTree[p].start && val <= segmentTree[p].end ) {
segmentTree[p].count += 1;
}
// 终止条件
if (segmentTree[p] === undefined) {
return ;
}
if (segmentTree[p].start === val && segmentTree.end === val) {
return ;
}
// 继续递归左右子线段树
if (segmentTree[2 * p + 1] !== undefined && val >= segmentTree[2 * p + 1].start && val <= segmentTree[2 * p + 1].end) {
setElement(val, 2 * p + 1);
}
if (segmentTree[2 * p + 2] !== undefined && val >= segmentTree[2 * p + 2].start && val <= segmentTree[2 * p + 2].end) {
setElement(val, 2 * p + 2);
}
}
// 在线段树中查找比当前元素小的元素的个数，因为是倒序遍历 nums 数组，所以，当前线段树中比当前元素小的元素一定是它右侧的元素
function searchRightBigCount(el, p) {
if (segmentTree[p] === undefined) {
return ;
}
// 如果当前线段树的区间完全包含在 el 的线段中
if (segmentTree[p].start >= el.start && segmentTree[p].end <= el.end) {
c += segmentTree[p].count;
return ;
}
// 如果当前线段树与 el 的线段无交叉，终止递归
if (el.end < segmentTree[p].start || el.start > segmentTree[p].end) {
return ;
}
// 如果当前线段树和 el 的线段有交叉，那么把 el 与 当前线段树交集部分的线段赋值给 el，
// 继续遍历左右子线段树
if (el.start <= segmentTree[p].start && el.end >= segmentTree[p].start) {
el.start = segmentTree[p].start;
searchRightBigCount(el, 2 * p + 1);
searchRightBigCount(el, 2 * p + 2);
}
else if (el.start <= segmentTree[p].end && el.end >= segmentTree[p].end) {
el.end = segmentTree[p].end;
searchRightBigCount(el, 2 * p + 1);
searchRightBigCount(el, 2 * p + 2);
}
}
// 倒序遍历数组 nums，一边将元素填入线段树，一遍计算它右侧元素的个数
for (let i = nlen - 1; i >= 0; i--) {
setElement( nums[i], 0 );
if (min > nums[i] - 1) {
ans[i] = 0;
} else {
searchRightBigCount({ start: min, end: nums[i] - 1 }, 0);
ans[i] = c;
}
c = 0;
}
return ans;
}
//巧妙
/*
参考作者 NoBey
1.把 nums 正序排序，放到一个新的数组中
2.遍历 nums ，去这个新数组中找到他的索引位置就可以了，索引值就是比他小的个数
3.注意，每次找完一个元素，需要把他在新数组中删掉，因为他如果比下一个要删查找的元素小的话，回导致下一个元素的索引
错误，因为他是下一个元素左边的元素，题目要求是：求他右边比他小的元素；
同时还有一个好处就是：防止因为元素重复导致错误
4.优化的一点是 forEach 直接在原数组操作，没有使用新的内存空间
*/
var countSmaller = function(nums) {
let newArr = [...nums].sort((a, b) => a - b);
nums.forEach((v, k) => {
let index = newArr.indexOf( v );
nums[k] = index;
newArr.splice(index, 1);
});
return nums;
}