排序算法案例

发表于 | 更新于 | 分类于 | 阅读次数： | 字数： 5,580 | 阅读时长： 27

题目：调整数组顺序使奇数位于偶数前面

输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前班部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

解题思想：

方案1：​ 归并排序的思想。利用辅助空间进行排序，判断每个数，如果是奇数放入数组的左边，如果是偶数从右边开始放。

方案2：快速排序的思想。不需要辅助空间，利用两个指针，从最左边和最右边的数判断，如果左指针指向的数为偶数，右指针指向的数为奇数，交换着两个数。

java实现代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class 调整数组顺序_奇左偶右 {

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(10);
		util.ArrayUtil.printArr(arr);
		megerAdjust(arr);
		util.ArrayUtil.printArr(arr);
		quickAdjust(arr);
		util.ArrayUtil.printArr(arr);
	}
	
	//归并思想，开辟辅助空间，进行调整
	public static void megerAdjust(int[] arr) {
		int[] helper = new int[arr.length];
		//left:指向调整数组的左边，都是奇数，right：指向右边，偶数
		int left = 0, right = arr.length-1;
		int current = 0; //指向原数组的待调整数
		System.arraycopy(arr, 0, helper, 0, arr.length);
		while(current < arr.length) {
			if(helper[current] % 2 == 1) {
				arr[left++] = helper[current++];
			}else {
				arr[right--] = helper[current++];
			}
		}
	}
	
	//快速排序思想，不需要辅助空间。
	public static void quickAdjust(int[] arr) {
		int left = 0, right = arr.length - 1;
		while(left < right) {
			if(arr[left] % 2 == 1) {
				left++;
			}
			if(arr[right] % 2 == 0) {
				right--;
			}
			if(arr[left] % 2 == 0 && arr[right] % 2 == 1){
				util.Swap.swap(arr, left, right);
				left++;
				right--;
			}
		}
	}
}

程序执行结果：

1
2
3
51 29 34 65 22 55 89 58 51 61 
51 29 65 55 89 51 61 58 22 34 
51 29 65 55 89 51 61 58 22 34

题目：第K个元素

以尽量高的效率求出一个乱序数组中按数值顺序的第k个元素。

解题思想：

利用分区法的思想。每次找到一个中位数主元，将小于主元的放左边，大于主元的放右边。递归寻找。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class 第k小数 {

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(10);
		util.ArrayUtil.printArr(arr);
		QuickSort1.quickSort(arr, 0, arr.length - 1);
		util.ArrayUtil.printArr(arr);
		int K = selectK(arr, 0, arr.length - 1, 3);
		System.out.println("K = " + K);
		
	}
 
	public static int selectK(int[] arr, int p, int r, int k) {
        //调用快速排序中寻找主元的方法
		int q = QuickSrot.partition2(arr, p, r);//主元的下标
		int qK = q - p + 1;//主元是第几个元素
		if(qK == k) return arr[q];
		else if (qK > k) return selectK(arr, p, q - 1, k);
		else return selectK(arr, q + 1, r, k - qK);
	}
}

程序运行结果：

1
2
3
74 90 98 8 82 21 5 30 32 49 
5 8 21 30 32 49 74 82 90 98 
K = 21

题目：超过一半的数字

数组汇总有一个数字出现的次数超过了数组长度的一半，找出这个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.util.Arrays;

public class MoreThanHalf {
	//找出数组中出现次数过半的元素
	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 3, 3, 6, 6, 4, 3, 3, 3, 3};
		solve1(arr);
		solve2(arr);
		solve3(arr);
	}
	//解法1：排序后返回中间的元素。时间复杂度：O(nlg(n))
	public static void solve1(int [] arr) {
		Arrays.sort(arr);
		System.out.println(arr[arr.length/2]);
	}

	//解法2：顺序统计，O(n)
	//该题解法调用了找第k个数的方法。
	public static void solve2(int[] arr) {
		int k = chapter3_排序.第k小数.selectK(arr, 0, arr.length-1, arr.length/2);
		System.out.println(k);
	}

	//解法3：不同的数进行消除
	/*不同的数，进行消除，O(N)*/
	public static void solve3(int[] arr) {
		//候选数，先定位第一个元素
		int candidate = arr[0];
		//出现的次数
		int nTimes = 1;
		//扫描数组
		for (int i = 1; i < arr.length; i++) {
			//两两消减为0，应该把现在的元素作为候选值
			if (nTimes == 0) {
				candidate = arr[i];
				nTimes = 1;
				continue;
			}
			//遇到和候选值相同的，次数加1
			if (arr[i] == candidate)
				nTimes++;
			//不同的数，进行消减
			else
				nTimes--;
		}
		System.out.println(candidate);
	}

}

程序运行结果：

1
2
3
3
3
3

变化：出现的数恰好为总数的一半，求出这个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 //变化，出现次数恰好为个数的一半，求出这个数
  /*
  * 关于加强版水王的题我有个想法可以扫描一遍数组就解决问题：
    水王占总数的一半，说明总数必为偶数；
    不失一般性，假设隔一个数就是水王的id，两两不同最后一定会消减为0
    水王可能是最后一个元素，每次扫描的时候，多一个动作，和最后一个元素做比较，单独计数，计数恰好等于一半
    如果不是，计数不足一半，那么去掉最后一个元素，水王就是留下的那个candidate*/
  public static void solve5(int[] arr) {
    int candidate = arr[0];
    int nTimes = 0;
    int countOfLast = 0;//统计最后这个元素出现的次数
    int N = arr.length;
    for (int i = 0; i < N; i++) {
      //增加和最后一个元素比较的步骤
      if (arr[i] == arr[N - 1])
        countOfLast++;

      if (nTimes == 0) {
        candidate = arr[i];
        nTimes = 1;
        continue;
      }
      if (arr[i] == candidate)
        nTimes++;
      else
        nTimes--;
    }
    //最后一个元素出现次数是n/2
    if (countOfLast == N / 2)
      System.out.println(arr[N - 1]);
    else
      System.out.println(candidate);
  }

  public static void main(String[] args) {
    solve3(new int[]{0, 1, 2, 1, 1});
  }
}

题目：最小可用ID

在非负数组（乱序）中找到最小的可分配的id（从1开始编号），数量1000000.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class 最小可用id {
	public static void main(String[] args) {
		int[] arr = {3, 1, 2, 6, 9, 4, 10, 13, 7};
		System.out.println(find1(arr));
		System.out.println(find2(arr, 0, arr.length-1));
	}

	//方法1：新建长为n+1的数组，初始全为0，扫描原数组中的元素，将小于
	//总数n的对应的位置标记为1，最后再扫描辅助数组，第一个为0的元素下标即为最小可用id
	private static int find1(int[] arr) {
		int[] helper = new int[arr.length+1];
		for(int i = 0; i < arr.length; i++) {
			if(arr[i] <= arr.length - 1)
				helper[arr[i]] = 1;
		}
		for(int i = 1; i <= arr.length; i++) {
			if(helper[i] == 0) {
				return i;
			}
		}
		return arr.length + 1;
	}
	
	//方法2：递归,不需要辅助空间
	public static int find2(int[] arr, int l, int r) {
		if(l > r) 
			return l + 1;
		int midIndex = l + ((r - l) >> 1);//中间下标
		//实际在中间位置的值
		int q = chapter3_排序.第k小数.selectK(arr, l, r, midIndex - l + 1);
		int t = midIndex + 1; //期望值
		if(q == t) { //左侧紧密
			return find2(arr, midIndex + 1, r);
		}else {
			return find2(arr, l, midIndex - 1);
		}
	}
}

题目：合并有序数组

给定两个排序后的数组A和B，其中A的末端有足够的空间容纳B。编写一个方法，将B合并入A并排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class 合并有序数组 {

	public static void main(String[] args) {
		//模拟a有足够空间
		int[] a = {1, 2, 6, 9, 10, 13, 15, 0, 0, 0, 0, 0, 0, 0};
		int[] b = {3, 4, 5, 7, 8};
		meger(a, b);
		util.ArrayUtil.printArr(a);
	}

	//解法：利用归并的思想，从大到小排序
	private static void meger(int[] a, int[] b) {
		int aMax = 7 - 1;//假设a有7个数。a的有序数组的最大数的下标
		int bMax = b.length - 1;
		int right = 7 + b.length - 1;
		while(bMax >= 0) {
			if(b[bMax] >= a[aMax]) {
				a[right--] = b[bMax--];
			}else {
				a[right--] = a[aMax--];
			}
		}
	}
}

程序运行结果：

1
1 2 3 4 5 6 7 8 9 10 13 15 0 0

题目：逆序对个数

一个数列，如果左边的数大，右边的数小，则称这两个数位一个逆序对。求出一个数列中有多少个逆序对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package chapter3_排序;

public class 逆序对个数 {

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(10);
		util.ArrayUtil.printArr(arr);
		System.out.println(niXu(arr));
		System.out.println(niXu2(arr));
	}

	//方法1：暴力破解，时间复杂度O(n)
	private static int niXu(int[] arr) {
		int sum = 0;
		for(int i = 0; i < arr.length; i++) {
			for(int j = i+1; j < arr.length; j++) {
				if(arr[j] < arr[i]){
					sum++;
				}
			}
		}
		return sum;
	}

	//方法2：利用归并排序思想。时间复杂度nlg(n)
	//在每次比较两个有序数组时，如果取右边的的数时，左边数组剩余的个数即为逆序对
	static int[] helper; //辅助空间，和arr的长度一样
	static int niXu = 0;
	public static int niXu2(int[] arr) {
		helper = new int[arr.length];
		megerSort(arr, 0, arr.length- 1);
		return niXu;
	}
	public static void megerSort(int[] arr, int p, int r) {
		if(p < r) {
			int mid = p + ((r - p) >> 1);
			megerSort(arr, p, mid);
			megerSort(arr, mid + 1, r);
			meger(arr, p, mid, r);
		}

	}
	
	private static void meger(int[] arr, int p, int mid, int r) {
		System.arraycopy(arr, p, helper, p, r - p + 1);
		int left = p; // 左侧队伍的头部指针，指向待比较的元素
		int right = mid + 1; //右侧队伍的头部指针，指向待比较的元素
		int current = p; //原数组的指针，指向待填入数据的位置
		while(left <= mid && right <= r) {
			if(helper[left] <= helper[right]) {
				arr[current++] = helper[left++];
			}else {
				arr[current++] = helper[right++];
				niXu += mid - left + 1;
			}
		}
		//如果左侧队伍没比较完，需要将左侧的数依次添加到原队列后面
		while(left <= mid) {
			arr[current++] = helper[left++];
		}
	}

}

程序运行结果：

1
2
3
97 40 30 69 78 55 84 5 6 62 
27
27

二叉树与数组：

将二叉树存储在数组中，并遍历二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package chapter3_排序;

public class TreeAndArray {

	public static void main(String[] args) {
		/*Tree:
		 *           1
		 *          / \
		 *         2   3
		 *        / \ / \
		 *       4  5 6  7
		 */
		int[] tree = {1, 2, 3, 4, 5, 6, 7};
		System.out.print("先序遍历：");
		preOrder(tree, 0);
		System.out.println();
		System.out.print("中序遍历：");
		inOrder(tree, 0);
		System.out.println();
		System.out.print("后序遍历：");
		posOrder(tree, 0);
	}
	//先序遍历
	public static void preOrder(int[] arr, int index) {
		if(index >= arr.length) return;
		System.out.print(arr[index] + " ");
		preOrder(arr, index * 2 + 1);
		preOrder(arr, index * 2 + 2);
	}
	//中序遍历
	public static void inOrder(int[] arr, int index) {
		if(index >= arr.length) return;
		inOrder(arr, index * 2 + 1);
		System.out.print(arr[index] + " ");
		inOrder(arr, index * 2 + 2);
	}
	//后序遍历
	public static void posOrder(int[] arr, int index) {
		if(index >= arr.length) return;
		posOrder(arr, index * 2 + 2);
		posOrder(arr, index * 2 + 1);
		System.out.print(arr[index] + " ");
	}
}

程序运行结果：

1
2
3
先序遍历：1 2 4 5 3 6 7 
中序遍历：4 2 5 1 6 3 7 
后序遍历：7 6 3 5 4 2 1

题目：排序数组中找和的因子

给定已排序数组arr和k，不重复打印arr中所有相加为和为k的不降序二元组。

如输入arr={-8, -4, -3, 0, 2, 4, 5, 8, 9, 10}, k = 10

输出：（0， 10）（2， 8）

解题思路：

方案1：暴力法，时间复杂度O(n^2)

方案2：二分法，时间复杂度O(nlgn)

方案3：二指针扫描。时间复杂度O(n)

java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import java.util.Arrays;

public class 排序数组中和为k的因子 {
	public static void main(String[] args) {
		int[] arr = {-8, -4, -3, 0, 2, 4, 5, 8, 9, 10};
		System.out.print("方案1输出：");
		solve1(arr, 10);
		System.out.print("方案2输出：");
		solve2(arr, 10);
		System.out.print("方案3输出：");
		solve3(arr, 10);
	}
	//暴力法
	public static void solve1(int[] arr, int k) {
		for(int i = 0; i < arr.length; i++) {
			for(int j = i + 1; j < arr.length; j++) {
				if(arr[i] + arr[j] == k) {
					System.out.print("(" + arr[i] + "," + arr[j] + ")");
				}
			}
		}
		System.out.println();
	}
	//二分法
	public static void solve2(int[] arr, int k) {
		for(int i = 0; i < arr.length; i++) {
			int value = k - arr[i];
			int result = Arrays.binarySearch(arr, i + 1, arr.length, value);
			if(result >= 0) {
				System.out.print("(" + arr[i] + "," + arr[result] + ")");
			}
		}
		System.out.println();
	}
	//双向扫描法
	public static void solve3(int[] arr, int k) {
		int left = 0;
		int right = arr.length - 1;
		while(left < right) {
			if(arr[left] + arr[right] == k) {
				System.out.print("(" + arr[left] + "," + arr[right] + ")");
				left++;
			}else if(arr[left] + arr[right] < k){
				left++;
			}else {
				right--;
			}
		}
		System.out.println();
	}
}

程序运行结果：

1
2
3
方案1输出：(0,10)(2,8)
方案2输出：(0,10)(2,8)
方案3输出：(0,10)(2,8)

题目：需要排序的子数组

给定一个无序数组arr，求出需要排序的最短子数组长度。

要求：时间复杂度O（n）

如输入：arr={2， 3， 7， 5， 4， 6}，返回4，因为只有{7， 5， 4， 6}需要排序。

java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class 需要排序的子数组长度 {
	/*有一个整数数组，存在索引a和b，只要将a和b之间的元素排好序，整个数组就是有序（升序）的。
	注意：b-a应该越小越好，也就是说，找出符合条件的最短序列。

	给定一个int数组A和数组的大小n，请输出a和b，若原数组有序，输出0和0。保证A中元素均为正整数。

	测试样例：
	6
	1 4 6 5 9 10
	输出：2 3
	 */
	public static void main(String[] args) {
		int[] A = {1, 4, 6, 5, 9, 10};
		int[] res = findSegment(A, 6);
		util.ArrayUtil.printArr(res);

		A = new int[]{1, 2, 3, 4, 5, 6};
		res = findSegment(A, A.length);
		util.ArrayUtil.printArr(res);

		A = new int[]{1, 5, 3, 4, 2, 6, 7};
		res = findSegment(A, A.length);
		util.ArrayUtil.printArr(res);

		A = new int[]{2, 3, 7, 5, 4, 6};
		res = findSegment(A, A.length);
		util.ArrayUtil.printArr(res);
		
		A = new int[]{3, 2, 5, 6, 7, 8};
		res = findSegment(A, A.length);
		util.ArrayUtil.printArr(res);

		A = new int[]{2, 8, 7, 10, 9};
		res = findSegment(A, A.length);
		util.ArrayUtil.printArr(res);

		A = new int[]{2, 3, 7, 4, 1, 5, 6};
		res = findSegment(A, A.length);
		util.ArrayUtil.printArr(res);

	}
//A = new int[]{2, 3, 7, 4, 1, 5, 6, 8, 5};
	public static 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};
	}
}

程序运行结果：

1
2
3
4
5
6
7
2 3 
0 0 
1 4 
2 5 
0 1 
1 4 
0 6

题目：前k个数

求海量数据（正整数）按逆序排列的前k个数（topk），因为数据量太大，不能全部存储在内存中，只能一个一个地从磁盘或者网络上读取数据，请设计一个高效的算来解决这个问题。

第一行：用户输入k，代表用求得的topK

随后的N（不限制）行，每一行是一个正整数代表用户输入的数据。用户每输入一个数据就回车使得程序可以立即获得这个数据，用户输入-1代表输入终止。

请输出topK，从小到大，空格分割。

解题思路：

思路：维持一个一个k大的数组，每次输入数，与k个数组中最小的比较，如果大于最小的，与最小的进行交换，重复执行这个操作，最后剩下的就是最大的k个数。

解法1：时间复杂度Kn，如果每次在数组中用顺序扫描法寻找最小数的的时间复杂度是k，N个数，所以总时间复杂度kN。

解法2：利用小顶堆，可将时间复杂度降到NlgK.

解法1代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.Arrays;
import java.util.Scanner;

public class TopK {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		//开辟k个空间的数组，用来存放最大的k个数
		int[] arr = new int[k];
		int x = sc.nextInt();
		int num = 0;//计数，检查输入数据数量是否超过k个数
		int min = 0; //记录数组中的最小值
		int minIndex = 0;//记录数组中最小数所在下标
		while (x != -1) {
			//当输入小于k个数时，直接加入数组
			if(num < k) {
				arr[num++] = x;
				if(num == k) { 
					//当输入数据等于k时，寻找最小值
					min = minOf(arr)[0];
					minIndex = minOf(arr)[1];
				}
			}else {//当输入数据量大于k时，此时每输入一个数和
				//已经存在数据中的第一个进行比较，如果小于数组中最小的数，
				//则不做操作，继续输入下一个数，如果大于第一个数，则替换第一个数，
				//重新进行排序。
				//因为arr是每次排好序的数组，所以arr[0]是数组中最小的数
				if(x > min) {
					arr[minIndex] = x;
					min = minOf(arr)[0];
					minIndex = minOf(arr)[1];
				}
			}
			x = sc.nextInt();
		}
		util.ArrayUtil.printArr(arr);
	}

	private static int[] minOf(int[] arr) {
		int min = arr[0];
		int minIndex = 0;
		for(int i = 0; i < arr.length; i++) {
			if(min > arr[i]) {
				min = arr[i];
				minIndex = i;
			}
		}
		Arrays.sort(arr);
		return new int[] {min, minIndex};
	}
}

程序运行结果：

1
2
3
4
5
6
7
8
3
123
12
12
23
35
-1
23 35 123

解法2代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.Arrays;
import java.util.Scanner;

public class TopK2 {

	static int[] topK;
	static int k;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		k = sc.nextInt();
		//开辟k个空间的数组，用来存放最大的k个数
		topK = new int[k];
		int x = sc.nextInt();
		int num = 0;
		while (x != -1) {
			if(num < k) {
				topK[num++] = x;
				if(num == k) {
					makeMinHeap(topK);
				}
			}else {
				if(topK[0] < x) {
					topK[0] = x;
					minHeapFixDown(topK, 0, k);
				}
			}
			x = sc.nextInt();
		}
		Arrays.sort(topK);
		util.ArrayUtil.printArr(topK);
	}

	public static void makeMinHeap(int[] arr) {
		int n = arr.length;
		for(int i = n / 2 - 1; i >= 0; i--) {
			minHeapFixDown(arr, i, n);
		}
	}

	public static void minHeapFixDown(int[] arr, int i, int n) {
		//左右孩子下标
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		//左孩子越界
		if(left >= n) return;
		int min = left;
		if(right >= n) { //右孩子越界
			min = left;
		}else{
			//找出左右孩子较小值得下标
			if(arr[left] > arr[right]) {
				min = right;
			}
		}
		//如果arr[i] <= arr[min]，不用调整
		if(arr[i] <= arr[min]) {
			return;
		}
		//否则交换两个数
		int tmp = arr[i];
		arr[i] = arr[min];
		arr[min] = tmp;
		minHeapFixDown(arr, min, n);
	}
}

程序运行结果：

1
2
3
4
5
6
7
8
9
4
23
2
3
4
15
245
-1
4 15 23 245

题目：所有员工年龄排序

公司现在要对几万员工的年龄进行排序，因为公司的人数非常多，所以要求排序算法的效率非常高，你能写出这样的程序吗

输入：输入可能包含多个测试样例，对于每个测试案例，

  • 输入的第一行为一个整数n（1<=n <=1000000）：代表公司内员工人数。
  • 输入的第二行包括n个整数:代表公司内每个员工的年龄。其中员工年龄的取值范围为（1 <= age <= 99）

输出：对应每个测试案例，

  • 请输出排序后的n个员工的凝练，每个年龄后面有一个空格

解题思想：

因为年龄段是固定的，所以可以利用计数排序的思想进行排序，时间复杂度可达到O(n)

java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Scanner;

public class AgeSort {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] age = new int[n];
		for(int i = 0; i < n; i++) {
			int x = sc.nextInt();
			age[i] = x;
		}
		ageSort(age);
		util.ArrayUtil.printArr(age);
	}
	//利用计数排序的思想，性能达到O(n)
	public static void ageSort(int[] arr) {
		int[] helper = new int[100];
		for(int i = 0; i < arr.length; i++) {
			helper[arr[i]]++;
		}
		int current = 0;
		for(int i = 1; i < 100; i++) {
			while(helper[i] != 0) {
				arr[current++] = i;
				helper[i]--;
			}
		}
	}

}

程序运行结果：

1
2
3
4
5
6
7
5
12
24
99
34
12
12 12 24 34 99

题目：数组能排成的最小数（特殊排序）

输入一个正整数数组，把数组里所有的整数拼接起来排成一个数，打印出能拼接的所有数字中最小的一个。

例如：输入数组{3,32,321}，则打印出3这个数字能排成的最小数字为：321323

解题思路：

利用api的Arrays.sort，在排序过程中传入比较器，自己定义比较的规则。进行排序。

java示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Arrays;
import java.util.Comparator;

public class 特殊排序 {

	public static void main(String[] args) {
		int res = sort(new Integer[] {3, 32, 321});
		System.out.println(res);
		res = sort(new Integer[] {3, 234, 23, 42});
		System.out.println(res);
	}

	public static int sort(Integer[] arr) {
		Arrays.sort(arr, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				String s1 = o1 + "" + o2;
				String s2 = o2 + "" + o1;
				return s1.compareTo(s2);
			
		});
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < arr.length; i++) {
			sb.append(arr[i]);
		}
		return Integer.parseInt(sb.toString());
	}
}

程序执行结果：

1
2
321323
23234342

题目：数组的包含

输入两个字符串str1和str2，请判断str1中的所有字符是否都存在str2中。

java代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Arrays;
import java.util.zip.Adler32;

public class 判断数组的包含问题 {

	public static void main(String[] args) {
		String s1 = "abc";
		String s2 = "adfjldscsac";
		String s3 = "bcdefa";
		System.out.println("s1是否包含在s2中：" + check(s1, s2));
		System.out.println("s1是否包含在s3中：" +check(s1, s3));
	}

	public static boolean check(String s1, String s2) {
		char[] s2_arr = s2.toCharArray();
		Arrays.sort(s2_arr);
		for(int i = 0; i < s1.length(); i++) {
			char a = s1.charAt(i);
			int index = Arrays.binarySearch(s2_arr, a);
			if(index < 0) {
				return false;
			}
		}
		return true;
	}
}

程序运行结果:

1
2
s1是否包含在s2中：false
s1是否包含在s3中：true
坚持原创技术分享，您的支持将鼓励我继续创作！