字符串和数组排序

随机抽取

洗牌

洗牌算法

步骤

将数组分为以弄混和为弄混两部分
随机从未弄混(包含自己)拿出一个和未弄混的最后一个位置进行调换
标记最后一个为已弄混
重复步骤

137. 只出现一次的数字 II

这种题通常有要考虑只能用到O(1)的空间复杂度
两种思路:
1. 使用位运算,类似异或的手法消除多余的数字(这个通常很难想到,需要用到状态机之类的)
2. 创建一个32位的数组,直接遍历所有数字每个bit都加1,然后判断最后哪个bit不是倍数再组装出一个数字结果

水塘抽样

给你一个未知长度的单链表，请你设计一个算法，只能遍历一次，随机地返回链表中的一个节点

遇到第 i 个元素时，应该有 1/i 的概率选择该元素，1 - 1/i 的概率保持原有的选择

int getRandom(ListNode head) {
    Random r = new Random();
    int i = 0, res = 0;
    ListNode p = head;
    // while 循环遍历链表
    while (p != null) {
        i++;
        // 生成一个 [0, i) 之间的整数
        // 这个整数等于 0 的概率就是 1/i
        if (0 == r.nextInt(i)) {
            res = p.val;
        }
        p = p.next;
    }
    return res;
}

带权重的抽样

使用前缀和区间划分方法,将不同权重等效为区间长度
使用二分搜索快捷查找区间的映射关系

三路快排

// 三路快排 
void qsort(int arr[],int l,int r)
{
	if(l>=r) return;
	int i=l,j=l,k=r;
	int val=arr[l+rand()%(r-l+1)];

	while(i<=k) {
		if(arr[i]<val) 
			swap(arr[i++],arr[j++]); // 这里可，前面是安全的。 
		else if(val<arr[i]) 
			swap(arr[i],arr[k--]); // 这里 i 不能 ++, 还要判断一下后面扔过来的东西。 
		else i++;
	}
	
	qsort(arr,l,j-1); qsort(arr,k+1,r);
}

堆排

按顺序建立二叉树
递归查找每个子树最大值,调整树

#include <iostream>  
#include <algorithm>  
using namespace std;  
  
void max_heapify(int arr[], int start, int end) {  
    // 建立父節點指標和子節點指標  
    int dad = start;  
    int son = dad * 2 + 1;  
    while (son <= end) { // 若子節點指標在範圍內才做比較  
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的  
            son++;  
        if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數  
            return;  
        else { // 否則交換父子內容再繼續子節點和孫節點比較  
            swap(arr[dad], arr[son]);  
            dad = son;  
            son = dad * 2 + 1;  
        }  
    }  
}  
  
void heap_sort(int arr[], int len) {  
    // 初始化，i從最後一個父節點開始調整  
    for (int i = len / 2 - 1; i >= 0; i--)  
        max_heapify(arr, i, len - 1);  
    // 先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢  
    for (int i = len - 1; i > 0; i--) {  
        swap(arr[0], arr[i]);  
        max_heapify(arr, 0, i - 1);  
    }  
}

归并排序

将数组分割成为两个更加小的数组
然后让小的数组有序,再合并成大的数组

void merge(vector<int>& arr, int l, int m, int r) {
    // 计算左右两个子数组的长度
    int n1 = m - l + 1;
    int n2 = r - m;
    // 创建临时的左右两个子数组
    vector<int> L(n1), R(n2);
    // 将原数组的数据拷贝到临时的左右两个子数组中
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    // 合并左右两个子数组至原数组
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 将剩余元素加入到已经排好序的结果中
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        // 计算中间位置
        int m = l + (r - l) / 2;

        // 递归排序左右两个子数组
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // 将已经排好序的子数组合并成为整体有序的数组
        merge(arr, l, m, r);
    }
}

基数排序-164.最大间距

给定一个无序的数组 `nums`，返回 _数组在排序之后，相邻元素之间最大的差值_ 。如果数组元素个数小于 2，则返回 `0` 。
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

基数排序的时间复杂度为O(d * (n + k))，其中d是最大数字的位数，n是要排序的数字个数，k是桶的大小。因为需要进行d次排序，每次排序需要遍历一遍数组并将数字放到对应的桶中，再遍历一遍桶中数字的位置信息，因此总时间复杂度为O(d * (n + k))。
基数排序的空间复杂度也为O(n + k)，即需要一个长度为n的原数组和一个长度为k的桶数组来存储数据。因为桶的大小取决于数字的范围，因此它通常比要排序的数字个数小得多，空间复杂度往往被认为是线性的。

// 获取数组中最大值
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// 基数排序实现
void radixSort(int arr[], int n) {
    // 获取要排序数组中最大数字
    int max = getMax(arr, n);

    // 进行桶排序（按每个位数进行排序）
    for (int exp = 1; max / exp > 0; exp *= 10) {
        int bucket[10] = { 0 };

        // 将数字放到对应的桶中
        for (int i = 0; i < n; i++) {
            bucket[(arr[i] / exp) % 10]++;
        }

        // 更新桶中数字的位置信息
        for (int i = 1; i < 10; i++) {
            bucket[i] += bucket[i - 1];
        }

        // 将数字按其在桶中的位置放回原数组
        int output[n];
        for (int i = n - 1; i >= 0; i--) {
            output[bucket[(arr[i] / exp) % 10] - 1] = arr[i];
            bucket[(arr[i] / exp) % 10]--;
        }

        // 更新原数组
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
}

计数排序

找出待排序的数组中最大和最小的元素,创建数组C
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

KMP字符串匹配

核心是生成next数组,主串指针永远不向后移动,之后自串指针根据数组的对应值进行移动
不匹配时候,子串指针根据数组数据移动到对应下标位置
next数组的生成完全由子串自己决定和控制,和主串无关,生成最长公共前缀方法,思路使用动态规划的思想
1. 遍历每一个数字,双指针方法,左边i是已经匹配的指针,右边j是目前的指针
2. 当左右不相同时候开始移动,左边指针移动到next[j-1]位置,因为这个位置是公共前缀的下一个位置,循环直到成功

void getNext(int m){
	int j = 0;
	// 初始化next[0]的值
	kmp_next[0] = 0;
	for(int i=1; i<m; ++i){
		// 当这一位不匹配时，将j指向此位之前最大公共前后缀的位置
		while(j>0 && b[i]!=b[j]) j=kmp_next[j-1];
		// 如果这一位匹配，那么将j+1，继续判断下一位
		if(b[i]==b[j]) ++j;
		// 更新next[i]的值
		kmp_next[i] = j;
	}
}
int kmp(int n,int m){
	int i, j = 0;
	// 初始化位置p = -1
	int p = -1;
	// 初始化next数组
	getNext(m);
	for(i=0; i<n; ++i){
		// 当这一位不匹配时，将j指向此位之前最大公共前后缀的位置
		while(j>0 && b[j]!=a[i]) j=kmp_next[j-1];
		// 如果这一位匹配，那么将j+1，继续判断下一位
		if(b[j]==a[i]) ++j;
		// 如果是子串(m位完全匹配)，则更新位置p的值，并中断程序
		if(j==m){
			p = i - m + 1;
			break;
		}
	}
	// 返回位置p的值
	return p;
}

时间复杂度为O(m+n)(移动主串指针m加上生成数组的n),空间复杂度为O(n)(子串数组长度)

chenxuan'blog