网站营销方案设计公司,微信 微网站,建设网站如何选择服务器,广东网站开发公司电话方法一 排序法#xff1a; 2*n长度的数组里面有一个元素重复了n次#xff0c;那么将数组排序#xff0c;求出排序后数组的中间值#xff08;因为长度是偶数#xff0c;没有刚好的中间值#xff0c;默认求的中间值是偏左边的那个#xff09;那么共有三种情况#xff1a;…
方法一 排序法 2*n长度的数组里面有一个元素重复了n次那么将数组排序求出排序后数组的中间值因为长度是偶数没有刚好的中间值默认求的中间值是偏左边的那个那么共有三种情况
重复n次的元素为最小值那么数组前一半都是该元素此时中间值也是该元素重复n次的元素为最大值那么数组后一半都是该元素此时中间值后面一个就是该元素既不是最大值也不是最小值那么中间值也一定就是该元素
var repeatedNTimes function(nums) {nums.sort((a,b)a-b)var mid Math.floor((nums.length-1)/2)if(nums[mid]nums[mid-1] || nums[mid]nums[mid1])return nums[mid]else if(nums[mid1]nums[mid2]) return nums[mid1]
};
消耗时间和内存情况 方法二 Map集合
用map记录nums里的各元素各出现了多少次出现了n次即可返回
var repeatedNTimes function(nums) {var len nums.length/2var map new Map()for(let n of nums){if(map.has(n)){map.set(n,map.get(n)1)if(map.get(n)len) return n}else{map.set(n,1)}}
};
消耗时间和内存情况 方法三 数学方法
考虑重复元素x在nums中出现的位置
如果相邻的x之间至少都隔了2个位置那么数组的总长度至少为n2n-13*n - 2
当n2时3n-2 2n 不存在满足要求的数组。因此一定存在两个相邻的x它们的位置是连续的或者只隔了1个位置
当n2时数组的长度最多为2n4因此最多只能隔2个位置。
所以我们只需要遍历所有间隔2个位置及以内的小标对判断对应的元素是否相等即可
var repeatedNTimes function(nums) {const n nums.length;for (let gap 1; gap 3; gap) {for (let i 0; i gap n; i) {if (nums[i] nums[i gap]) {return nums[i];}}}// 不可能的情况return -1;
};
