An array of

Lookup in a two-dimensional array

/ * * *@param {number[][]} array
 * @param {number} target
 * @return {boolean}* /
var searchArray = function(array , target) {
    // Left => right, up => Down increment ==> You can start from the upper right corner
    if(! array.length)return false;
    let n = array.length;
    let i = 0, j = array[0].length - 1;
    while(i < n && j >= 0) {if(array[i][j] > target) j--;
        else if(array[i][j] < target) i ++;
        else return true;
    }
    
    return false;
};
Copy the code

Fibonacci numbers

/ * * *@param {number} n
 * @return {number}* /
var Fibonacci = function(n)
{
    let ans = [];
    ans[0] = 0;
    ans[1] = 1
    for(let i = 2; i <= 39; i ++){
        ans[i] = ans[i-1] + ans[i-2];
    }
    
    return ans[n];  
}
Copy the code

Reorder the array so that the odd number precedes the even number

1. The original order is not maintained

/ * * *@param {number[]} array
 * @return {void}* /
var reOrderArray = function(array) {
    
    let l = 0, r = array.length - 1;
    while(l < r){
        while(l < r && array[l] % 2= = =1) l ++;
        while(l < r && array[r] % 2= = =0) r--;
        if(l < r) {
            lett = array[l]; array[l] = array[r]; array[r] = t; }}};Copy the code

2. Keep the order

/** * The class name, method name, and parameter name have been specified, do not modify, directly return method specified value ** *@param Array int One-dimensional array *@return Int One-dimensional array */
function reOrderArray( array ) {
    // write code here
    const arr1 = [];
    const arr2 = [];
    let length = array.length;
    for(let i = 0; i < length; i ++) {
        if(array[i] % 2= = =1){
            arr1.push(array[i]);
        }else{ arr2.push(array[i]); }}return arr1.concat(arr2);
}
module.exports = {
    reOrderArray : reOrderArray
};
Copy the code

Print the matrix clockwise

function printMatrix(matrix)
{
    // write code here
    const res = [];
    const n = matrix.length;
    if(! n)return res;
    const m = matrix[0].length;
    
    let dx = [0.1.0, -1];
    let dy = [1.0, -1.0];
    const st = new Array(n).fill(0).map(() = > new Array(m).fill(false));
    
    let x = 0, y = 0, d = 0;
    for(let i = 0; i < m * n ; i ++) {
        res.push(matrix[x][y]);
        st[x][y] = true;
        let a = x + dx[d], b = y + dy[d];
        if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
            d = (d + 1 ) % 4; 
            a = x + dx[d];
            b = y + dy[d];
        }
        x = a, y = b;    
    }
    return res;
    
}
Copy the code

The number that occurs more than half The Times in an array

Very clever, notation

function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    let count = 1;
    let val = numbers[0];
    for(let i = 1; i < numbers.length; i ++) {
        if(val ! == numbers[i]) { count --;if(count < 0) {
                count = 1; val = numbers[i]; }}else{ count ++; }}return val;
}
Copy the code

Arrange the array to the smallest number

/ * * *@param {number[]} nums
 * @return {string}* /
var printMinNumber= function(nums) {
    if(! nums || nums.length ===0) return "";
    else return nums.sort(compare).join("");
};

var compare = function(a,b){
    const q = "" + a + b;
    const h = "" + b + a;
    return q - h;
}
Copy the code

Pairs of inversions in an array

/ * * *@param {number[]} nums
 * @return {number}* /
var inversePairs= function(nums) {
    
    
    let res = 0;
    mergeSort(nums, 0, nums.length - 1);
    return res;
    
    
    function mergeSort(nums, l, r){
        if(l >= r) return ;
        let mid = l + r >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid+1, r);
        let k = 0;
        let i = l, j = mid + 1;
        let tmp = [];
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]){
                tmp.push(nums[i++]);
            }else{
                res += mid - i + 1; tmp.push(nums[j++]); }}while(i <= mid) tmp.push(nums[i++]);
        while(j <= r) tmp.push(nums[j++])
        for(i = l,j = 0; i <= r; i ++, j ++){ nums[i] = tmp[j]; }}};Copy the code

The number of occurrences of a number in an ascending array

function GetNumberOfK(data, k)
{
    // write code here
    if(data.indexOf(k) < 0) return 0;
    let l = data.indexOf(k);
    let r = data.lastIndexOf(k);
    return r - l + 1;
    
}
Copy the code

And two numbers of S

function FindNumbersWithSum(array, sum)
{
    // write code here
    if(! array)return []
    let l = 0, r = array.length - 1;
    while(l < r) {
        if(array[l] + array[r] === sum ) return [array[l], array[r]];
        else if(array[l] + array[r] > sum) r --;
        else l ++;
    }
    return [];
}
Copy the code

Duplicate numbers in an array

/ * * *@param {number[]} nums
 * @return {number}* /
var findRepeatNumber = function(nums) {
    let map = new Map(a);for(let i = 0; i < nums.length; i ++){
        if(map.has(nums[i])) return nums[i];
        else map.set(nums[i],1);
    }
    return null;
};
Copy the code

Building product Arrays

function multiply(a)
{
    // write code here
    const res = [];
    let left = [];
    let right = [];
    left[0] = right[a.length - 1] = 1;
    for(let i = 1; i < a.length; i ++) {
        left[i] = left[i -1] * a[i - 1];
    }
    for(let j = a.length-2; j>=0 ; j--){
        right[j] = a[j+1] * right[j+1];
    }
    for(let k=0; k<a.length; k++){ res[k] = left[k] * right[k]; }return res;
    
}
Copy the code