JAVA算法：在给定的一维数组中找到最小的前3个数

JAVA算法：在给定的一维数组中找到最小的前3个数

问题描述：给定一个一维整型数组，写一个算法找到最小的前3个整数

举例：

给定整型数组 a = { 6, 8, 1, 9, 2, 10};
输出为： 1， 2， 6
给定整型数组 a = { 6, 8, 1, 9, 2, 1, 10, 10};
输出为： 1，1， 2
给定整型数组  a = {6};
输出为： Invalid Input, array size is less than 3

问题分析

给定一维整型数组，要找到其中最小的前3个数。不能使用Arrays类中的sort方法，需要自己写算法。

那么不妨先设置3个变量：first，second，third，假设其为整型的最大值：Integer.MAX_VALUE

设定一个当前用于进行比较的变量current；current的初始值取数组的第1个元素值。

之后随着循环比较（循环变量为i，0<i<数组的长度），current每次代表当前下标为 i 的数组元素。

这样，我们使用数组 a = { 6, 8, 1, 9, 2, 10} 进行推演比较过程。

推演过程

first，second，third的初始值均设置为最大：2147483647 

当i=0时，取数组中的第1个元素赋给current，此时current=6，然后进行比较，比较的结果是: first=6；second=2147483647；third=2147483647

当i=1时，取数组中的第2个元素赋给current，此时current=8，然后进行比较:
                此时 first=6，first<current;再用second与current进行比较，此时second>second，则将current赋给second，
                比较结果为：first=6,；second=8；third=2147483647
当i=2时，取数组中的第3个元素赋给current，此时current=1，然后进行比较：
               此时first=6，显然大于current，则将current赋给first，first得到1，second得到原来的first，即6，

               third得到原来的second，即8；
               比较结果为：first=1；second=6；third=8

               经过前3次的取数和比较，可以看出first，second，third已经形成了一个升序的序列。
               并且，通过每次的比较，确保first都存放的是最小的一个值，second存放的是第二大的值，third存放的是第三大的值；

当i=3时，取数组中的第4个元素赋给current，此时current=9，然后进行比较:
                由于first，second，third的当前值都小于current的值，所以比较之后first，second，third的值均不变，
                 即仍然为： first=1；second=6；third=8
当i=4时，取数组中的第5个元素赋给current，此时current=2，然后进行比较：
                由于first=1，first的值不用更新；而second此时的值为6，显然second>current，

                则将third的值更新为当前second的值，即third=6；
                再将second的值更新为当前的current，即second=2，
                更新之后的结果为：first=1；second=2；third=6

算法设计

package com.bean.algorithm.beginner;

public class ThreeSmallestElement {
	public static void leastThreeElements(int[] arrA) {
		//当数组长度小于3时，提示无效输入
		if (arrA.length < 3) {
			System.out.println("Invalid Input, array size is less than 3");
		}
		//设定三个值分别为：first，second，third
		int first = Integer.MAX_VALUE;
		int second = Integer.MAX_VALUE;
		int third = Integer.MAX_VALUE;
		//遍历数组元素
		for (int i = 0; i < arrA.length; i++) {
			//将第i个元素赋给当前值current
			int current = arrA[i];
			//如果first大于current，则把current赋给first，first最小
			if (first > current) {
				//这个就好比空出位置来，2->3;1->2;current->1
				third = second;
				second = first;
				first = current;
			} else if (second > current) {//如果second大于current
				//则当前的second赋给third
				third = second;
				//current赋值给second
				second = current;
			} else if (third > current) {//如果third大于current
				//则current赋值给third
				third = current;
			}
		}
		System.out.println("least three elements are: " + first + " " + second + " " + third);
	}

	public static void main(String[] args) {
		int[] arrA = new int[] { 6, 8, 1, 9, 2, 10 };
		leastThreeElements(arrA);
	}
}

程序运行结果

least three elements are: 1 2 6