Viewing JS array through V8

Why is it JavaScript in , You can save different types of values in an array , And the array can be dynamically increased ⻓？

 stay Chrome V8 in ,JSArray  Inherit  JSObject, Inside with  key-value  Form storage data , Therefore, different types of values can be stored. It has two storage methods ： A fast array using contiguous memory space   and   A slow array in the form of a hash table initializes an empty array with a fast array , When the array length reaches the maximum  JSArray  super-popular , When in an array  hole  Too many will turn into slow arrays , To save memory space 

One 、 Common array method encapsulation

1、 flat

const flattenDeep = (array) => array.flat(Infinity)

2、 duplicate removal

const unique1 = (array) => Array.from(new Set(array))const unique2 =  arr => [...new Set(arr)]const unique3 = arr => {  return arr.sort().reduce((pre, cur) => {    if (!pre.length || pre[pre.length - 1] !== cur) {      pre.push(cur)    }    return pre  }, [])}const unique4 = arr => {  return arr.filter((el, index, array) => array.indexOf(el) === index)}

3、 Sort

const sort = (array) => array.sort((a, b) => a-b)

4、 Function combination

const compose = (...fns) => (initValue) => fns.reduceRight((y, fn) =>fn(y), initValue)//  Combined function const flatten_unique_sort = compose( sort, unique, flattenDeep)//  test var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ]] ], 10]console.log(flatten_unique_sort(arr)) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

5、 intersection

const intersection = function (nums1, nums2) {  return [...new Set(nums1.filter((el) => nums2.includes(el)))]};

Set Is a collection of non repeating values ( In his opinion NaN Equal to itself ), towards Set When adding value , No type conversion will occur , The key name is the key value

Two 、 Commonly used array method implementation

1. map Realization

map The method is a pure function , Without changing the length of the array

Array.prototype.myMap = function(callbackfn, thisArg) {  const newArr = []  for (let i = 0; i < this.length; i++) {    newArr.push(callbackfn.call(thisArg, this[i], i, this))  }  return newArr}console.log([1, 2, 3].myMap(i => i * i))

2. reduce Realization

reduce The method is a pure function , It is used to convert arrays into objects 、 Other types such as numeric strings

Array.prototype.myReduce = function(callbackfn, initialValue = null) {  for (let i = 0; i < this.length; i++) {    initialValue = callbackfn(initialValue, this[i], i, this)    // initialValue = callbackfn.call(thisArg, initialValue, this[i], i, this)  }  return initialValue}console.log([1, 2, 3].myReduce((pre, cur) => pre + cur))

3. filter Realization

reduce The method is a pure function , Will change the array length

Array.prototype.myFilter = function(callbackfn, thisArg) {  const newArr = []  for (let i = 0; i < this.length; i++) {    callbackfn.call(thisArg, this[i], i, this) && newArr.push(this[i])  }  return newArr}console.log([1, 2, 3].myFilter(i => i >= 2))

3、 ... and 、leetcode The most common related questions

1、 Merge two ordered arrays

Here are two buttons Non decreasing order Array of arranged integers  nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in . Would you please Merge nums2 To nums1 in , Make the merged array press Non decreasing order array . Final , The merged array should not be returned by the function , It's stored in an array nums1 in ,nums1 The initial length of is m + n

 Example :   Input : nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3   Output : [1,2,2,3,5,6] //  Need merger  [1,2,3]  and  [2,5,6]   The combined result is  [1,2,2,3,5,6]

Ideas ：

• Prerequisite ： Ordered array 、 The first array just meets the space of the second array
• establish num1 And num2 Length variable len1、len2 And total length len
• In turn len1、len2 Compare the corresponding elements , Fill in the larger one num1 Of len Location , And corresponding length -1
• When len2 < 0, That is, those that need to be merged num2 All written num1, The loop ends
• When len2 > 0, and len1 < 0, be num1 The element of is larger than num2, And has written , At this point, just put num2 You can fill in the elements that have not been merged in turn

const merge = (num1, m, num2, n) => {  let len = m + n - 1;  let len1 = m - 1;  let len2 = n - 1;  while (len2 > -1) {    if (len1 < 0) {      num1[len--] = num2[len2--];      continue;    }    num1[len--] = num1[len1] > num2[len2] ? num1[len1--] : num2[len2--]  }  return num1;}

2、 Sum of two numbers

Given an array of integers nums  And an integer target value target, Please find... In the array And is the target value target  The two integers of , And return their array subscripts . You can assume that each input There will be only one answer . however , Array The same element In the answer Can't repeat appear , The answers can be returned in any order

 Example :   Input : nums = [2,7,11,15], target = 9   Output : [0,1] //  because  nums[0] + nums[1] == 9 , return  [0, 1]

Ideas ：

• use hashMap Store traversed elements and corresponding indexes
• One element per iteration , have a look hashMap Whether there is a target number that meets the requirements in

var twoSum = function(nums, target) {    let map = {}    for(let i = 0; i < nums.length; i++) {      if(map[target - nums[i]]) {          return [map[target - nums[i]]-1,i]      }else {         map[nums[i]] = i+1      }    }};

3、 Sum of three numbers

Give you one containing n Array of integers nums, Judge nums Are there three elements in a ,b ,c , bring a + b + c = 0 ？ Please find out all the conditions that meet and No repetition Triple of

 Example :   Input : nums = [-1, 0, 1, 2, -1, -4]   Output : [          [-1, 0, 1],          [-1, -1, 2]        ]

Ideas ：

• First, sort the array
• Traversing an ordered array ： With nums[i] For the first number first, And nums[first+1]、nums[nums.length - 1] For the second left、 Third right The initial value of the
• left、right Judge in the form of double pointers ： Whether the sum of the three numbers is 0, if < 0 be left++;>0 be right--;=0 Then collect the result and shift the pointer accordingly . Continue to judge the next tuple , until right > left End of cycle , At this time, use nums[i] Tuples that satisfy the condition as the first number have been written to
• repeat 2、3 step , Continue traversing nums[i], until i === nums.length - 2
• Last , Because it is not repeatable , So after getting the first element and adding the qualified tuple , Perform the corresponding de duplication

const threeSum = function (nums) {  //  Sentenced to empty   if (!nums || nums.length < 3) return [];  //  Sort   nums.sort((a, b) => a - b);  const res = [];  for (let first = 0; first < nums.length - 2; first++) {    //  duplicate removal     if (first > 0 && nums[first] === nums[first - 1]) continue;    let left = first + 1;    let right = nums.length - 1;    while (left < right) {      const sum = nums[left] + nums[right] + nums[first];      if (!sum) {        res.push([nums[left], nums[right], nums[first]]);        //  duplicate removal         while (left < right && nums[left] === nums[left + 1]) left++;        while (left < right && nums[right] === nums[right - 1]) right--;        left++;        right--;      } else {        sum < 0 ? left++ : right--;      }    }  }  return res;}

4、 Delete duplicates in array

Here's an ordered array nums , Would you please In situ Delete duplicate elements , Make each element appear only once , Returns the new length of the deleted array . Don't use extra array space , You must be there. In situ Modify the input array and use O(1) Complete with extra space

 Example :   Input : nums = [1,1,2]   Output : 2, nums = [1,2] //  Function should return the new length  2 , And the original array  nums  The first two elements of are modified to  1, 2 . You don't need to think about the elements in the array that follow the new length .

Ideas ：

• Delete in place , And you can't use extra space , You can only traverse the current array and operate , You can use the speed pointer , The fast pointer acts as a traverser , The slow pointer collects information
• If fast pointer is not equal to slow pointer , Then the two elements are different , At this point, the slow pointer advances one step , And set the value of the fast pointer to the next value of the slow pointer , Otherwise, the slow pointer will not move

var removeDuplicates = function (nums) {  let slow = 0;  for (let fast = 1; fast < nums.length; fast++) {    if (nums[slow] !== nums[fast]) {      slow++;      nums[slow] = nums[fast]    }  }  return slow + 1;}

5、 Move zero

Given an array nums, Write a function that will 0 Move to end of array , meanwhile Keep the relative order of non-zero elements

 Example :   Input : [0,1,0,3,12]   Output : [1,3,12,0,0]

Ideas ：

• Use the speed pointer , The fast pointer acts as a traverser
• When the value of the fast pointer is not 0 when , Swap position with slow pointer , At the same time, the slow pointer takes a step forward

var moveZeroes = function (nums) {  let slow = 0;  let fast = 0;  while (fast < nums.length) {    if (!!nums[fast]) {      //  Interchange location       [nums[slow], nums[fast]] = [nums[fast], nums[slow]]      slow++;    }    fast++;  }  return nums}

6、 Intersection of two arrays II

Here are two arrays of integers  nums1 and nums2 , Please return the intersection of two arrays as an array . Returns the number of occurrences of each element in the result , It should be consistent with the number of occurrences of elements in both arrays （ If the number of occurrences is inconsistent , Then consider taking the smaller value ）. You can ignore the order of the output results

 Example :   Input : nums1 = [1,2,2,1], nums2 = [2,2]   Output : [2,2]

Ideas ：

• It can also be solved through the idea of front and back pointers , The difference is that two pointers are placed in two arrays
• Sort two arrays , Move the pointer down by comparing the size , When the size is consistent, the value is pushed
• Traverse the boundary ： Any pointer exceeds the array it is in

var intersect = function (nums1, nums2) {  let slow = 0;  let fast = 0;  const res = [];  nums1.sort((a, b) => a - b)  nums2.sort((a, b) => a - b)  while (slow < nums1.length && fast < nums2.length) {    if (nums1[slow] === nums2[fast]) {      res.push(nums1[slow])      fast++;      slow++;    } else if (nums1[slow] > nums2[fast]) {      fast++    } else {      slow++    }  }  return res;};