Web Front-endJS TutorialSample code for solving the median problem of two ordered lists using JavaScriptSample code for solving the median problem of two ordered lists using JavaScript
Arrange the numbers in a sequence from small to large. At this time, the variable value located in the middle is called the median value.
So, given two ordered lists, how to find their common median?
When you get this problem, the first solution you think of is to merge the two ordered lists, then sort them in ascending order, and finally take out the median value at once.
This approach is very simple and convenient, but it is not very efficient. Because of the sorting, it is an algorithm of O(N*logN).
So, how to optimize?
You can refer to the algorithm for merging ordered linear lists:
1. Use two pointers to point to the current ordered list, and use a new array to receive the comparison of smaller array elements.
2. Compare the array elements pointed to by the two pointers, store the smaller one in the new array, and move the pointer backward. This process will continue until one of the pointers is empty, or the median value has been received by the new array, then the median value will be returned directly.
3.If after phase 2 is completed, a pointer is non-null, and the middle value is not received by the new array at this time, then continue to use the pointer to traverse the ordered list , until the median value is received, return it.
4.The optimized algorithm is O(m+n), and the efficiency is greatly improved.
var findMedianSortedArrays = function(nums1, nums2) {
//两个列表的总元素个数
var totalLength = nums1.length + nums2.length;
//总元素个数是否为奇数
var isOdd = totalLength % 2 === 0 ? false : true;
//两个指针
var p1 = 0;
var p2 = 0;
//用于接收的新数组
var array = [];
//只要指针仍然在范围内
while(p1 < nums1.length && p2 < nums2.length){
//将较小的元素压入新数组，指针后移
if(nums1[p1] < nums2[p2]){
array.push(nums1[p1]);
p1++;
}
else{
array.push(nums2[p2]);
p2++;
}
//如果此时已接收中值,弹出中值，返回
if(array.length === totalLength / 2 + 1){
return (array.pop() + array.pop()) / 2;
}
if(isOdd && array.length === Math.ceil(totalLength / 2)){
return array.pop();
}
}
//有一个指针已经出界了
//此时仍然没有接收到中值
//对另一个指针继续遍历
//直到接收中值,弹出中值，并返回
while(p1 < nums1.length){
array.push(nums1[p1]);
if(array.length === totalLength / 2 + 1){
return (array.pop() + array.pop()) / 2;
}
if(isOdd && array.length === Math.ceil(totalLength / 2)){
return array.pop();
}
p1++;
}
while(p2 < nums2.length){
array.push(nums2[p2]);
if(array.length === totalLength / 2 + 1){
return (array.pop() + array.pop()) / 2;
}
if(isOdd && array.length === Math.ceil(totalLength / 2)){
return array.pop();
}
p2++;
}
};The above is the detailed content of Sample code for solving the median problem of two ordered lists using JavaScript. For more information, please follow other related articles on the PHP Chinese website!
Understanding the JavaScript Engine: Implementation DetailsApr 17, 2025 am 12:05 AMUnderstanding how JavaScript engine works internally is important to developers because it helps write more efficient code and understand performance bottlenecks and optimization strategies. 1) The engine's workflow includes three stages: parsing, compiling and execution; 2) During the execution process, the engine will perform dynamic optimization, such as inline cache and hidden classes; 3) Best practices include avoiding global variables, optimizing loops, using const and lets, and avoiding excessive use of closures.
Python vs. JavaScript: The Learning Curve and Ease of UseApr 16, 2025 am 12:12 AMPython is more suitable for beginners, with a smooth learning curve and concise syntax; JavaScript is suitable for front-end development, with a steep learning curve and flexible syntax. 1. Python syntax is intuitive and suitable for data science and back-end development. 2. JavaScript is flexible and widely used in front-end and server-side programming.
Python vs. JavaScript: Community, Libraries, and ResourcesApr 15, 2025 am 12:16 AMPython and JavaScript have their own advantages and disadvantages in terms of community, libraries and resources. 1) The Python community is friendly and suitable for beginners, but the front-end development resources are not as rich as JavaScript. 2) Python is powerful in data science and machine learning libraries, while JavaScript is better in front-end development libraries and frameworks. 3) Both have rich learning resources, but Python is suitable for starting with official documents, while JavaScript is better with MDNWebDocs. The choice should be based on project needs and personal interests.
From C/C to JavaScript: How It All WorksApr 14, 2025 am 12:05 AMThe shift from C/C to JavaScript requires adapting to dynamic typing, garbage collection and asynchronous programming. 1) C/C is a statically typed language that requires manual memory management, while JavaScript is dynamically typed and garbage collection is automatically processed. 2) C/C needs to be compiled into machine code, while JavaScript is an interpreted language. 3) JavaScript introduces concepts such as closures, prototype chains and Promise, which enhances flexibility and asynchronous programming capabilities.
JavaScript Engines: Comparing ImplementationsApr 13, 2025 am 12:05 AMDifferent JavaScript engines have different effects when parsing and executing JavaScript code, because the implementation principles and optimization strategies of each engine differ. 1. Lexical analysis: convert source code into lexical unit. 2. Grammar analysis: Generate an abstract syntax tree. 3. Optimization and compilation: Generate machine code through the JIT compiler. 4. Execute: Run the machine code. V8 engine optimizes through instant compilation and hidden class, SpiderMonkey uses a type inference system, resulting in different performance performance on the same code.
Beyond the Browser: JavaScript in the Real WorldApr 12, 2025 am 12:06 AMJavaScript's applications in the real world include server-side programming, mobile application development and Internet of Things control: 1. Server-side programming is realized through Node.js, suitable for high concurrent request processing. 2. Mobile application development is carried out through ReactNative and supports cross-platform deployment. 3. Used for IoT device control through Johnny-Five library, suitable for hardware interaction.
Building a Multi-Tenant SaaS Application with Next.js (Backend Integration)Apr 11, 2025 am 08:23 AMI built a functional multi-tenant SaaS application (an EdTech app) with your everyday tech tool and you can do the same. First, what’s a multi-tenant SaaS application? Multi-tenant SaaS applications let you serve multiple customers from a sing
How to Build a Multi-Tenant SaaS Application with Next.js (Frontend Integration)Apr 11, 2025 am 08:22 AMThis article demonstrates frontend integration with a backend secured by Permit, building a functional EdTech SaaS application using Next.js. The frontend fetches user permissions to control UI visibility and ensures API requests adhere to role-base
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
SublimeText3 English version
Recommended: Win version, supports code prompts!
mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),
MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.
SublimeText3 Chinese version
Chinese version, very easy to use
SublimeText3 Mac version
God-level code editing software (SublimeText3)
