数组.md

专题_数组

N_sum
二分查找
找到数组中第K个数

N_sum 博客链接

// 要求数组有序

//2_sum
vector<vector<int>> twoSum(vector<int>& nums, int target, int st, int ed) {
    vector<vector<int> > res;
    while (st < ed) {
        if (nums[st] + nums[ed] == target) {
            if (res.empty() || res.back()[0] != nums[st]) {
                res.push_back(vector<int>{nums[st], nums[ed]});
            }
            ++st;
            --ed;
        } else if (nums[st] + nums[ed] > target) {
            --ed;
        } else {
            ++st;
        }
    }
    return res;
}

//n_sum
vector<vector<int>> nSum(vector<int>& nums, int target, int st, int ed, int n) {
    vector<vector<int> > res;
    if (n == 2) {
        return twoSum(nums, target, st, ed);
    } else {
        for (int i=st; i<=ed; ++i) {
            int num = nums[i];
            if (res.empty() || res.back()[0] != num) {
                auto ret = nSum(nums, target-num, i+1, nums.size()-1, n-1);
                for (auto r : ret) {
                    vector<int> tmp;
                    tmp.push_back(num);
                    tmp.insert(tmp.end(), r.begin(), r.end());
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
}

二分查找 模板链接

// 方法1 [l, mid]和[mid + 1, r]
// 模板
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
// 实例，升序，从左往右，第一个 >= NumberToFind的元素
int bsearch_1(int l, int r,int arr[],int NumberToFind){
    while (l < r){
        int mid = l + r >> 1;
        if (arr[mid] >= NumberToFind) r = mid;
        else l = mid + 1;
    }
    printf("%d",l);
    return l;
}

// 方法2 [l, mid - 1]和[mid, r]
// 模板
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
// 实例，升序，从右往左，第一个 <= NumberToFind的元素
int bsearch_1(int l, int r,int arr[],int NumberToFind){
    while (l < r){
        int mid = l + r + 1>> 1;
            if (arr[mid] <= NumberToFind) l = mid;
        else r = mid - 1;
    }
    printf("%d",l);
    return l;
}

找到数组中第K个数

• 第一次使用整个快排
• 接下来每次丢掉快排的一边

# python
def quicksort(num ,low, high):  # 快速排序
    if low < high:
        location = partition(num, low, high)
        quicksort(num, low, location - 1)
        quicksort(num, location + 1, high)

def partition(num, low, high):
    pivot = num[low]
    while (low < high):
        while (low < high and num[high] > pivot):
            high -= 1
        while (low < high and num[low] < pivot):
            low += 1
        temp = num[low]
        num[low] = num[high]
        num[high] = temp
        if(num[low]==num[high]):
            high -= 1
    num[low] = pivot
    return low


def findkth(num, low, high, k):  # 找到数组里第k个数
    index = partition(num, low, high)
    if index == k: return num[index]
    if index < k:
        return findkth(num, index + 1, high, k)
    else:
        return findkth(num, low, index - 1, k)

pai = [2, 3, 1, 5, 4, 6]
# quicksort(pai, 0, len(pai) - 1)
print(findkth(pai, 0, len(pai) - 1, 5))

cpp版

// cpp
int partition(vector<int> vec, int low, int high) {
	int pre = vec[low];
	while(low < high){
		while(low < high && vec[high] > pre) high--;
		while(low < high && vec[low] < pre) low++;
		int temp = vec[low];
		num[low] = vec[high];
		vec[high] = temp;;
		if(vec[low] == vec[high]) high--;
	}
	vec[low] = pre;
	return low;
}

// 第K小的数
int topK(vector<int> vec, int low,int high, int k) {
	int index = partition(num, low, high);
	if (index == k) {
		return vec[low];
	}
	if (index < k) {
		return topk(vec, index + 1, high, k);
	}
	else return topk(vec, low, index-1, k);
}