題目描述
陣列中有一個數字出現的次數超過陣列長度的一半，請找出這個數字，例如輸入一個長度為9的陣列{1,2,3,2,2,2,5,4,2}，由于數字2在陣列中出現了5次，超過陣列長度的一半，因此輸出2，如果不存在則輸出0，
思路
思路二：如果有符合條件的數字，則它出現的次數比其他所有數字出現的次數和還要多，
在遍歷陣列時保存兩個值：一是陣列中一個數字，一是次數，遍歷下一個數字時，若它與之前保存的數字相同，則次數加1，否則次數減1；若次數為0，則保存下一個數字，并將次數置為1，遍歷結束后，所保存的數字即為所求，然后再判斷它是否符合條件即可，
牛客網鏈接
js代碼
//方法一
function MoreThanHalfNum_Solution(numbers)
{
// write code here
const len = numbers.length
if (len === 0) return 0
const map = new Map()
for (let i of numbers) {
if (map.get(i) === undefined) {
map.set(i, 1)
}else {
map.set(i, map.get(i)+1)
}
}
for (let item of map.entries()) {
if (item[1] > Math.floor(len/2)) return item[0]
}
return 0
}
//方法二
function MoreThanHalfNum_Solution(numbers)
{
// write code here
if (numbers.length === 0) return 0
let res = numbers[0]
let times = 1
for (let i of numbers) {
if (times === 0) {
res = i
times = 1
}
else if (i === res) times++
else times--
}
times = 0
for (let i of numbers) {
if (i === res) times++
}
return times > Math.floor(numbers.length / 2)? res: 0
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138106.html
標籤：其他
上一篇：二叉樹創立及遍歷