在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
示例 :
输入: [7,5,6,4]
输出: 5
限制:
0 <= 数组长度 <= 50000
首先能想到使用暴力解法,双重循环,但时间复杂度为N方,显然有待改进。
可使用归并的方式实现
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function (nums) {
// 归并排序
let sum = 0;
mergeSort(nums);
return sum;
function mergeSort(nums) {
if (nums.length < 2) return nums;
const mid = parseInt(nums.length / 2);
let left = nums.slice(0, mid);
let right = nums.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let res = [];
let leftLen = left.length;
let rightLen = right.length;
let len = leftLen + rightLen;
for (let index = 0, i = 0, j = 0; index < len; index++) {
if (i >= leftLen) res[index] = right[j++];
else if (j >= rightLen) res[index] = left[i++];
else if (left[i] <= right[j]) res[index] = left[i++];
else {
res[index] = right[j++];
sum += leftLen - i;//在归并排序中唯一加的一行代码
}
}
return res;
}
};
无缝轮播的核心是制造一个连续的效果。最简单的方法就是复制一个轮播的元素,当复制元素将要滚到目标位置后,把原来的元素进行归位的操作,以达到无缝的轮播效果。
使用 React
结合 Hooks
实现核心代码片段如下:
useEffect(() => {
const requestAnimationFrame =
window.requestAnimationFrame || window.webkitRequestAnimationFrame || window.mozRequestAnimationFrame
const cancelAnimationFrame =
window.cancelAnimationFrame || window.webkitCancelAnimationFrame || window.mozCancelAnimationFrame
const scrollNode = noticeContentEl.current
const distance = scrollNode.clientWidth / 2
scrollNode.style.left = scrollNode.style.left || 0
window.__offset = window.__offset || 0
let requestId = null
const scrollLeft = () => {
const speed = 0.5
window.__offset = window.__offset + speed
scrollNode.style.left = -window.__offset + 'px'
// 关键行:当距离小于偏移量时,重置偏移量
if (distance <= window.__offset) window.__offset = 0
requestId = requestAnimationFrame(scrollLeft)
}
requestId = requestAnimationFrame(scrollLeft)
if (pause) cancelAnimationFrame(requestId)
return () => cancelAnimationFrame(requestId)
}, [notice, pause])
[1]
面试题51. 数组中的逆序对: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
本文分享自 JavaScript全栈 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!