我们知道在javascript中 可以在数组中保存不同类型的值 并且数组可以动态增长,不像其他语言 例如
C 创建的时候要决定数组的大小 如果数组满了 ,就要重新申请内存,这是为什么呢?
可从四个方面回答这个问题
数组基础入门
javascript中 数组为什么可以保存不同类型的值
javascript中 数组是如何存储的
javascript中 数组的动态扩容与减容
Javascript中JSArray继承自JSObject,或者说它是一个特殊的对象,内部是以key-value形式存储数据
所以javascript中的数组可以存放不同类型的值。
它有两种存储方式,快数组与慢数组,初始化数组时 使用快数组,快数组使用连续的内存空间
当数组长度达到最大时 JSArray会进行动态扩容 以储存更多的元素,相对于慢数组 性能要好很多
当数组hole太多时(数组长度太长时) 会转变成慢数组,即以哈希表的方式(key-value的形式)存储数据 以节省内存空间
已知如下数组:var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]; 编写一个程序将数组扁平化去除其中重复的部分 最终得到一个升序且不重复的数组 var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]; // 扁平化 let flatArray = arr.flat(4) // 去重 let disArr = Array.from(new Set(floatArray)) // 排序 let result = disArr.sort((a,b)=>a-b) console.log(result); const getArray = (arr, dep) => Array.from(new Set(arr.flat(dep))).sort() // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
给你两个有序整数数组nums1和nums2 请你将nums2合并到nums1中 使num1成为一个有序数组
说明:nums1和nums2的元素数量分别为m和n。
你可以假设nums1有足够的空间 (空间大于或等于m + n) 来保存nums2中的元素
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
nums1 、 nums2 有序,若把 nums2 全部合并到 nums1 ,则合并后的 nums1 长度为 m+n
我们可以从下标 m+n-1 的位置填充 nums1 ,比较 nums1[len1] 与 nums2[len2] 的大小,将最大值写入 nums1[len],即
nums1[len1]>=nums2[len2] ,nums1[len–] = nums1[len1–] ,这里 – 是因为写入成功后,下标自动建议,继续往前比较
否则 nums1[len–] = nums2[len2–]
边界条件:
若 len1 < 0 ,即 len2 >= 0 ,此时 nums1 已重写入, nums2 还未合并完,仅仅需要将 nums2 的剩余元素(0…len)写入 nums2 即可,写入后,合并完成
若 len2 < 0,此时 nums2 已全部合并到 nums1 ,合并完成
时间复杂度为 O(m+n)
代码实现:
const merge = function(nums1,m,nums2,n){ let len1 = m-1; let len2 = n-1; len = m + n -1; while(len2>=0){ if(len1<0){ nums1[len--] = nums2[len2--] continue } nums1[len--] = nums1[len1]>=nums2[len2]?nums1[len1--]:nums2[len2--] } }
给定一个整数数组nums和一个目标值target 请你在该数组中找到和为目标值的那两个整数,并返回他们的数组下标
你可以假设每种输入只会对应一个答案。但是 你不能重复利用这个数组中同样的元素
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路:
初始化一个map= new Map()
从第一个元素开始遍历nums
获取目标值与nums[i]的差值 即k = target - nums[i]
判断差值在map中是否存在
不存在(map.has(k)为false),则将nums[i]加入到map中(key为nums[i],value为i,方便查找map中是否存在某值)
并可以通过get方法直接拿到下标
存在(map.has(k)) 返回[map.get(k),i],求解结束
遍历结束 则nums中没有符合条件的两个数 返回[]
时间复杂度 O(n)
const twoSum = function(nums,target){ let map = new Map() for(let i =0;i<nums.length;i++){ let k = target-nums[1] if(map.has(k)){ return [map.get(k),i] } map.set(nums[i],i) } return [] }