2023-8-27

8-27

数组

题号 剑指 Offer 39. 数组中出现次数超过一半的数字

题目 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

这个问题有三种解法

1. 哈希表
2. 排序找中点
3. 摩尔投票法

解法一 哈希表法

function majorityElement(nums: number[]): number {
    const frequencyMap: Record<number, number> = {};

    for (const num of nums) {
        if (frequencyMap[num]) {
            frequencyMap[num]++;
        } else {
            frequencyMap[num] = 1;
        }

        // 如果某个数字的出现次数超过数组长度的一半，直接返回它
        if (frequencyMap[num] > nums.length / 2) {
            return num;
        }
    }

    // 根据题目假设，一定存在多数元素，所以这里不会走到
    return -1;
}

解法二 排序找中点法

function majorityElement(nums: number[]): number {
    let votes = 0,x=0
    for(let num of nums){
        if(votes ===0)x=num
        if(num===x)votes+=1
        else votes-=1
    }
    return x
};

解法三 摩尔投票法

可以这样理解

来一个理解起来更简单的~

假设有一个擂台，有一组人，每个人有编号，相同编号为一组，依次上场，没人时上去的便是擂主（x），若有人，编号相同则继续站着（人数+1），若不同，假设每个人战斗力相同，都同归于尽，则人数-1；那么到最后站着的肯定是人数占绝对优势的那一组啦~

function majorityElement(nums: number[]): number {
    let votes = 0,x=0
    for(let num of nums){
        if(votes ===0)x=num
        if(num===x)votes+=1
        else votes-=1
    }
    return x
};

题号剑指 Offer 40. 最小的k个数

题目 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

直接先上k佬的题解https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solutions/594591/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/

解法一 快速排序

function getLeastNumbers(arr: number[], k: number): number[] {
    quickSort(arr,0,arr.length-1)
    return arr.slice(0,k)
};

function quickSort(arr:number[],l:number,r:number):number[]{
    if(l>=r)return
    let i = l ,j = r
    while(i<j){
        while(i<j&& arr[j]>= arr[l])j--
        while(i<j&& arr[i]<= arr[l])i++
        swap(arr,i,j)
    }
    swap(arr,i,l)
    quickSort(arr,l,i-1)
    quickSort(arr,i+1,r)
}

function swap(arr:number[],i:number,j:number){
    let tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
}

解法二 快速排序后优化进行数组划分

function getLeastNumbers(arr: number[], k: number): number[] {
    if(k>=arr.length)return arr
    quickSort(arr,0,arr.length-1)
    function quickSort(arr:number[],l:number,r:number):number[]{
    if(l>=r)return
    let i = l ,j = r
    while(i<j){
        while(i<j&& arr[j]>= arr[l])j--
        while(i<j&& arr[i]<= arr[l])i++
        swap(arr,i,j)
    }
    swap(arr,i,l)
    if(k<i)quickSort(arr,l,i-1)
    if(k>i)quickSort(arr,i+1,r)
    if(k===i)return
    }
    return arr.slice(0,k)
};



function swap(arr:number[],i:number,j:number){
    let tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
}