一、原地哈希

直接看例題：題目鏈接
題目描述：
給你一個(gè)未排序的整數(shù)數(shù)組 nums ，請你找出其中沒有出現(xiàn)的最小的正整數(shù)。
請你實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 并且只使用常數(shù)級別額外空間的解決方案。

示例 1：

輸入：nums = [1,2,0]
輸出：3

示例 2：

輸入：nums = [3,4,-1,1]
輸出：2

示例 3：

輸入：nums = [7,8,9,11,12]
輸出：1

思路分析：
拿到這道題如果沒有限制條件很容易想到兩種方法，第一種就是哈希表+遍歷，第二種是排序+遍歷，但是第一種方法空間復(fù)雜度超限，第二種時(shí)間復(fù)雜度超限。
而這里就可以用原地哈希來做。
假設(shè)數(shù)組的長度為N，那么我們要找的數(shù)一定會(huì)在1 ~ N+1之間，因?yàn)閿?shù)組的下標(biāo)是0 ~ N，所以我們可以把當(dāng)前數(shù)組當(dāng)場哈希表。
具體實(shí)現(xiàn)：

把數(shù)字1放到下標(biāo)為0的位置，把數(shù)字2放到下標(biāo)1的位置，以此類推。也就是把數(shù)值為i的數(shù)映射到i - 1的位置。
當(dāng)遍歷到指定位置的時(shí)候，就把當(dāng)前位置的數(shù)字放到指定位置，把指定位置的數(shù)字替換回來，重復(fù)操作，知道nums[i] == i + 1，這樣遍歷到后邊的位置如果符合條件直接跳過。時(shí)間復(fù)雜度為O(N)。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++)
        {
            while(nums[i] != i + 1)
            {
                if(nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i] - 1])
                {
                    break;
                }
                int idx = nums[i] - 1;
                swap(nums[idx], nums[i]);
            }
        }
        for(int i = 0; i < n; i++)
        {
            if(nums[i] != i + 1)
            {
                return i + 1;
            }
        }
        return n + 1;
    }
};

二、快速冪

2.1 指數(shù)無負(fù)數(shù)

快速冪主要解決的是a^b % p的場景，如果正常算的話需要循環(huán)b次來計(jì)算。但是這是可以優(yōu)化的：

可以看到每個(gè)數(shù)都是上一個(gè)數(shù)的平方 % p

先不看取模，我們現(xiàn)在要求a^b，其實(shí)就是從這些數(shù)字里平湊出來。

舉個(gè)例子，現(xiàn)在要求3^5：
5的二進(jìn)制表示為0101：

那么我們就可以循環(huán)b，當(dāng)b & 1 != 0，結(jié)果就要乘上a，每次把b右移1，并且把a(bǔ)的值平方。

看一道例題：
題目鏈接

題目描述：

輸入格式

第一行包含整數(shù) n。
接下來 n 行，每行包含三個(gè)整數(shù) ai,bi,pi。

輸出格式

數(shù)據(jù)范圍

1≤n≤100000,1≤ai,bi,pi≤2×109

輸入樣例：

2
3 2 5
4 3 9

輸出樣例：

4
1

#include <iostream>

using namespace std;

long long qmi(int a, int b, int p)
{
    long long res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = (long long)res * a % p;
        }
        b >>= 1;
        // 每個(gè)數(shù)是上一個(gè)數(shù)的平方 % p
        a = (long long)a * a % p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int a, b, p;
        scanf("%d %d %d", &a, &b, &p);
        printf("%d\n", qmi(a, b, p));
    }
    return 0;
}

2.2 指數(shù)有負(fù)數(shù)

上面的指數(shù)都是整數(shù)，而如果指數(shù)含有負(fù)數(shù)呢？
當(dāng)b < 0 的時(shí)候，只需要做兩步即可：
1?? 把a(bǔ)變成 1 / a
2?? 把b變成-b

但是這里要注意當(dāng)b是-2^31，直接轉(zhuǎn)化成整數(shù)會(huì)導(dǎo)致越界，所以可以用一個(gè)long long型的變量臨時(shí)存儲(chǔ)。文章來源地址http://www.zghlxwxcb.cn/news/detail-490178.html

class Solution {
public:
    double myPow(double x, int n) {
        double res = 1;
        long long b = n;
        if(b < 0)
        {
            x = 1 / x;
            b = -b;
        }
        while(b)
        {
            if(b & 1)
            {
                res = res * x;
            }
            b >>= 1;
            x = x * x;
        }
        return res;
    }
};

到了這里，關(guān)于【算法】原地哈希與快速冪的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！