题7：排序数组中找和的因子
给定已排序数组，arr和k,不重复打印arr中所有相加和为k的不降序二元组
如输入arr={-8,-4,-3,0,2,4,5,8,9,10},k=10
输出(0,10)(2,8)
双指针
left=0;
right=arr.length-1;
left右移，若是arr[left]+arr[right]<k,left++;
若是>k,right--;
等于则输出
因为如果arr[left]+arr[right]<k，arr[right]为最大的值，arr[left]加上arr[right]都小于k,则说明arr[left]太小，与后面任何一个数相加都小于k,所以left++
right与left一样，若是arr[left]+arr[right]>k,则证明arr[right]太大了，与left后面的任何值相加都大于k
扩展:三元组呢？
i,j,g
首先，将数组排序，使用三指针法。
然后，使用三个指针i、j和g，分别指向数组中的第一个元素、第二个元素和最后一个元素。
在每一次迭代中，计算当前三个指针所指向的元素之和sum。
如果sum等于目标值，则将这个三元组加入结果集，并将指针i和j分别向右移动一位，k向左移动一位，并消重
如果sum小于目标值，则将指针j向右移动一位。
如果sum大于目标值，则将指针g向左移动一位。
//即先确定i的位置，j和k用双指针判断arr[j]+arr[g]==k-arr[i];
//注意j在i后第一个元素，k在最后一个位置
重复上述步骤，直到所有可能的三元组都被考虑过。
这种方法的时间复杂度为O(n^2)，其中n是数组的长度
题8:需要排序的子数组
给定一个无序数组arr,求出需要排序的最短子数组长度
要求:o(n)
如输入:arr={2,3,7,5,4,6},返回4，因为只有{7，5，4，6}需要排序
public int[] findSegment(int[] A,int n){
int p1=-1;
int p2=-1;
int max=A[0];
int min=A[n-1];
//扩展右端点，更新历史最高，只要右侧出现比历史最高低的，就应该将右边界扩展到此处
for(int i=0;i<n;i++){
if(A[i]>max)
{
max=A[i];
}
//只要低于历史高峰，就要扩展需要排序区间的右端点
if(A[i]<max)
p2=i;
}
//找左端点，更新历史最低，只要左侧出现比历史最低高的，就将左边界扩展到此处
for(int i=n-1;i>0;i--){
if(A[i]<min){
min=A[i];
}
if(A[i]>min)
p1=i;
}
if(p1==-1){//即都有序
return new int[]{0,0}//匿名数组（临时数组）
}
return new int[]{p1,p2};//返回区间p1到p2
}
题9按逆序排列的前k个数(topK)
求海量数据(正整数)按逆序排列的前k个数(topK),因为数据量太大，不能全部存储在内存中，只能一个一个地从磁盘或网络中上读取，请设计一个高效地算法来解决这个问题
第一行:用户输入k，代表要求topK
随后的N(不限制)行,每一行是一个整数嗲表用户输入的数据
用户输入-1代表输入终止
请输出topK，从小到大，空格分割
解决:大顶堆
static int[] heap;
static int size=0;
static int k;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int k=sc=nextInt();
heap=new int[k];//对heap进行初始化
int x=sc.nextInt();
while(x!=-1){
deal(x);//处理x
x=sc.next();
}
printRs();
}
private static void printfRs(){
Util.print(heap);
}
private static void deal(int x){
if(size<k){
heap(size++)=x;//x和堆顶进行比较
if(size==k){//当size=k时立即进行堆化
MinHeapFixDown(A,i,n);//上一节自己定义的方法，用于堆化
size++;
}
}else//x和堆顶比较,如果x大于堆顶，x将堆顶挤掉并向下调整
if(heap[0]<x)
{
heap[0]=x;
MinHeapFixDown(heap,0,k);//小顶堆，始终将最小的值挤走，然后堆化,最后剩下的就是最大的五个
printRs();//为了调试方便，每次都输出一下
}
}
题10:所有员工年龄排序
公司现在要对几万员工的年龄进行排序，因为公司员工的人数非常多，所以要求排序算法的效率要非常高，你能写出这样的程序吗
输入:输入可能包含多个测试样例，对于每个测试案例
-输入的第一行为一个整数n(1<=n<=1000000);代表公司员工的人数。
-输入的第二行包括n个整数:代表公司内每个员工的年龄。其中，员工年龄age的取值范围为(1<=age<=99 )
输出:对应每个测试案例
请输出排序后的n个员工的年龄，每个年龄后面有一个空格
int[] staffSort(int[] staff,int n){
int[99] helper;
for(int i=0;i<n;i++){
helper[staff[i]]++;
}
for(int i=0,j=0;i<99;i++){
while(helper[i]>0){
staff[j++]=i;
helper[i]--;
}
}
return staff;
}
题11:数组能排成的最小数(特殊排序)
输入一个正整数数组，把数组里所有整数拼接起来排成一个数，打印出能够拼接出的所有数字中最小的一个
例如输入数组{3,32,321},打印出这三个数字能排成的最小数字
为:321323
两两一组合，组合出来的数更小排到前面去
import。java.util.Arrays;
import java.util.Camparator;
public calss case{
public static void main(String[] args){
int res=f(new Integer[]{3,32,321});
System.out.println(res);
}
private static int f(Integer[] arr){
Arrays.sort(arr,new Comparator<Integer>(){//匿名的内部类，传一个比较器
//自定义比较规则
public int compa re(Integer a1,Integer a2){
String s1=o1+""+o2;
String s2=o2+""+o1;
return s1.compareTo(s2);//s1<s2返回-1，s1=s2返回0.s1>s2返回1
}
});//快排
StringBuilder sb=new StringBuilder();//StringBuilder线程不安全
for(int i=0;i<arr.length;i++){
sb.append(arr.[i]);//拼接字符串//后面追加
}
return Integer.parseInt(sb.toString());//字符换转为整形
//Integer.parseInt(sb.toString);
}
}
题12:数组的包含
输入两个字符串str1和str2,请判断str1中的所有字符是否都存在于str2中
public static boolean check(String s1,String s2){
for(int i=0;i<s1.length.i++){
char a=s1.charAt(i);
if(s2.indexOf(a)==-1){//查找字符在字符串中的位置
return false;//有一个没有就返回false
}
return true;
}
}
public static boolean check(String s1,String s2){
char[] s2_arr=s2.toCharArray();//将s2_arr转为字符数组
Array.sort(s2_arr);//再将字符数组排序
for(int i=0;i<s1.length();i++){//s1为字符串，用length(),若是字符数组用.length
char a=s1.charAt(i);//然后一个一个的找
//数组有序，用二分法查找，可大幅减少复杂度
int index=Arrays.binarySearch(s2_arr,a);//若是没找到，返回负数
if(index<0)
return false;
]
return true;
}
这道题主要调用了Java的类库，很多现成的类和方法都是JavaAPI里拥有的