作业解答

俩数之和||

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        //递减，满足相加之和为target
        for (int i = 0, j = numbers.length - 1; i < j;) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) return new int[] {i + 1, j + 1};
            else if (sum > target) j--;//大了，向左移动
            else i++;//小了，向右移动
        }
        return null;
    }
}

双调队列

#include<iostream>
using namespace std;
int n,a[1001];
int main()
{
    cin>>n;//输入 
    for(int i=1;i<=n;i++)cin>>a[i];//和输入 
    sort(a+1,a+n+1);//和排序 
    for(int i=1;i<=n/2;i++)
    {
        cout<<a[n-i+1]<<endl<<a[i]<<endl;//和输出 
    }
    if(n%2)cout<<a[n/2+1]<<endl;//和判定 
}

概念

排序，不同的算法书，有不同的解答，有的叫10大排序，有的叫8大排序，我们是按照十个来讲，
具体可以看下面这篇我早期写的文章：10大排序

冒泡排序

思想：
俩俩比较，如果反序交换，直到没有反序的记录为止，代码实现比较简单，是俩个for循环的嵌套

#include<iostream>
#include<algorithm>//调用算法库，使用交换函数swap
#include<cstdio>
using namespace std;
int main()
{
	int a[10];
	for (int i = 0; i < 10; i++)
	{
		cin >> a[i];

	}
	for (int i = 0; i < 10; i++)
	{
		for (int j = i + 1; j < 10; j++)
		{
			if (a[i] < a[j])
				swap(a[i], a[j]);
		}
	}
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

时间复杂度为O（n^2)

选择排序

我们发现，从第一个元素到最后一个元素中选择出一个最小的元素，和第一个元素进行交换，然后，从第二个元素到最后一个元素中选择出最小的元素，和第二个元素进行交换，最后，一定可以保证所有元素都是升序排列的

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
	int a[10];
	for (int i = 0; i < 10; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < 10; i++)
	{
		int min = i;
		for (int j = i + 1; j < 10; j++)
		{
			if (a[min] > a[j])
				min = j;//交换下标位置
		}
		if (i != min)
			swap(a[i], a[min]);
	}
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

刷题巩固

有序数组的平方
数组中最大书对和的最小值