Sword finger offer -- reverse order pair in array (JS Implementation)

Always_ positive 2021-05-03 13:20:55
sword finger offer reverse order


Title Description

Their thinking

  • I'm just beginning to see the problem , The first thing that comes to mind is violence , That is, through for Loop through and through , Result timeout .
  • Only after reading the explanation can we know , Solve the problem of reverse order , It's often sorted by merging
  • The essence of this question is to merge and sort , Just on the basis of merging and sorting , It's just a line of code .
  • Merging and sorting use the idea of divide and conquer , This question is based on the merger or not , Do statistical calculations , The final result is .

Solution code one ( Violence law : Overtime )

var reversePairs = function(nums) {
let flag = 0;
for (let i = 0; i < nums.length; i++) {
const temp = nums.slice(i+1);
for (let v of temp) {
if (v < nums[i]) {
flag++;
}
}
}
return flag;
};
 Copy code 

Problem solving code 2 ( Merge sort )

var reversePairs = function(nums) {
// ! Using the idea of merge sort 
// Define the number of variable storage reverse pairs 
let sum = 0;
// The return result of merge sort is assigned to sum
mergeSort(nums);
// Return the final result 
return sum;
// Merge sort function 
function mergeSort(nums) {
// If the length of the array is less than 2, When there is only one element , Let's return this array , The end condition of recursion 
if (nums.length < 2) return nums;
// If the length of the array is not less than 2, The explanation is not complete yet , Let's continue to divide 
let mid = Math.floor(nums.length / 2);
// The subarray on the left 
let left = nums.slice(0,mid);
// The subarray on the right 
let right = nums.slice(mid);
// Put the split left and right subarrays into the merge function 
return merge(mergeSort(left),mergeSort(right));
}
// Merge functions ( The user merges the split subarrays )
function merge(left,right) {
// Define a total array to store, merge, and order ( Containing left and right subarrays )
const res = [];
// The length of the left subarray 
const leftLen = left.length;
// The length of the right subarray 
const rightLen = right.length;
// Start loop traversal , In order to res Based on the subscript of (i Is the subscript of the left subarray ,j Is the subscript of the right subtree group ,index yes res The subscript )
for (let i = 0,j = 0,index=0;index < leftLen + rightLen; index++) {
// In the following judgment, we should first judge the condition of crossing the boundary 
if (i >= leftLen) {
// If i Cross border explanation , The left subarray has been traversed , here res Directly add the element pointed by the subscript of the right subarray 
res.push(right[j++])
} else if (j >= rightLen) {
// If j Transboundary , Indicates that the right subarray has been traversed , here res Directly add the element pointed by the subscript of the left subarray 
res.push(left[i++]);
} else if (left[i] <= right[j]) {
// If the element pointed to by the left subarray subscript is less than or equal to the element pointed to by the right subarray subscript , There is no reverse order pair at this time , Add the result of the left subarray to res The array can be 
res.push(left[i++])
} else {
// If the left subarray subscript points to more elements than the right subarray subscript points to , There is a reverse order pair 
res.push(right[j++]);
sum = sum + leftLen - i
}
}
// Returns the merged array ( It's easy to make mistakes here )
return res;
}
};
 Copy code 

summary ( The inspiration of this topic to us )

  • Revelation 1 : Learn to use merge sort
  • Revelation 2 : Learn to merge and sort the thought of divide and rule
版权声明
本文为[Always_ positive]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/05/20210503131221993o.html

  1. HTML + CSS + JavaScript to achieve cool Fireworks (cloud like particle text 3D opening)
  2. HTML + CSS + JavaScript realizes 520 advertising love tree (including music), which is necessary for programmers to express themselves
  3. Solve the problem of Web front-end deployment server (it can be deployed online without a server)
  4. HTML + CSS + JS make wedding countdown web page template (520 / Tanabata Valentine's Day / programmer advertisement)
  5. What else can driverless minibus do besides "Park connection"?
  6. Cloud native leads the era of all cloud development
  7. NRM mirror source management tool
  8. Bring it to you, flex Jiugong
  9. Lolstyle UI component development practice (II) -- button group component
  10. Deconstruction assignment in ES6
  11. Luo 2 peerless Tang clan was officially launched. The official gave a key point, and the broadcast time was implied
  12. 20初识前端HTML(1)
  13. 当新零售遇上 Serverless
  14. 20 initial knowledge of front-end HTML (1)
  15. When new retail meets serverless
  16. [golang] - go into go language lesson 5 type conversion
  17. [golang] - go into go language lesson 6 conditional expression
  18. HTML5(八)——SVG 之 path 详解
  19. HTML5 (8) -- detailed explanation of SVG path
  20. 需要开通VIP以后页面内容才能复制怎么办?控制台禁用javascript即可
  21. Web前端|CSS入门教程(超详细的CSS使用讲解,适合前端初学者)
  22. 实践积累 —— 用Vue3简单写一个单行横向滚动组件
  23. Serverless 全能选手,再下一城
  24. What if you need to open a VIP to copy the page content? Just disable JavaScript on the console
  25. Web front end | CSS introductory tutorial (super detailed CSS explanation, suitable for front-end beginners)
  26. Practice accumulation - write a single line horizontal scroll component simply with vue3
  27. Dili Reba is thin again. She looks elegant and high in a strapless hollow skirt, and her "palm waist" is beautiful to a new height
  28. Serverless all-round player, next city
  29. The difference between MySQL semi synchronous replication and lossless semi synchronous replication
  30. Vue表单设计器的终极解决方案
  31. The ultimate solution for Vue form designer
  32. Nginx从理论到实践超详细笔记
  33. Yu Shuxin's red backless swimsuit is split to the waist and tail, with a concave convex figure and excessive color matching, and his face is white to dazzling
  34. Nginx ultra detailed notes from theory to practice
  35. 【动画消消乐|CSS】086.炫酷水波浪Loading过渡动画
  36. typecho全站启用https
  37. CCTV has another popular employee. The off-site interpretation is very professional, and the appearance ability is no less than that of Wang Bingbing
  38. [animation Xiaole | CSS] 086. Cool water wave loading transition animation
  39. Enable HTTPS in Typecho
  40. 50天用JavaScript完成50个web项目,我学到了什么?
  41. 根据JavaScript中原生的XMLHttpRequest实现jQuery的Ajax
  42. What have I learned from completing 50 web projects with JavaScript in 50 days?
  43. "My neighbor doesn't grow up" has hit the whole network. There are countless horse music circles, and actor Zhou Xiaochuan has successfully made a circle
  44. 根据JavaScript中原生的XMLHttpRequest实现jQuery的Ajax
  45. Implement the Ajax of jQuery according to the native XMLHttpRequest in JavaScript
  46. Implement the Ajax of jQuery according to the native XMLHttpRequest in JavaScript
  47. 30 + women still wear less T-shirts and jeans. If they wear them like stars, they will lose weight
  48. 数栈技术分享前端篇:TS,看你哪里逃~
  49. Several stack technology sharing front end: TS, see where you escape~
  50. 舍弃Kong和Nginx,Apache APISIX 在趣链科技 BaaS 平台的落地实践
  51. Abandon the landing practice of Kong and nginx, Apache apisik on the baas platform of fun chain technology
  52. 浪迹天涯king教你用elementui做复杂的表格,去处理报表数据(合并表头,合并表体行和列)
  53. 前端HTML两万字图文大总结,快来看看你会多少!【️熬夜整理&建议收藏️】
  54. Wandering around the world king teaches you to use elementui to make complex tables and process report data (merge header, merge table body rows and columns)
  55. 路由刷新数据丢失 - vuex数据读取的问题
  56. Front end HTML 20000 word graphic summary, come and see how much you can【 Stay up late to sort out & suggestions]
  57. Route refresh data loss - vuex data reading problem
  58. Systemctl系统启动Nginx服务脚本
  59. Systemctl system startup nginx service script
  60. sleepless