Java数组的应用

1. 求数组种元素的平均值，给定一个整型数组，求平均值
   注意：因为是整型数组求平均值，在做除法的时候需要强制类型转换成double类型。

    public static double aveArray(int[] array) {
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }
        return (double) sum /array.length;
    }
    public static void main(String[] args) {
        //1.求数组中元素的平均值
        int[] array = {1,2,3,4};
        System.out.println(aveArray(array));
    }
1
2
3
4
5
6
7
8
9
10
11
12

运行结果：

2. 改变原有数组元素的值
实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2 , 并设置到对应的数组元素上. 例如 原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}

    public static void transform(int[] array) {
        for (int i = 0; i < array.length; i++) {
            array[i] = array[i] * 2;
        }
    }
    public static void main(String[] args) {
        //改变原有数组元素的值
        int[] array = {1,2,3};
        transform(array);
        System.out.println(Arrays.toString(array));
    }
1
2
3
4
5
6
7
8
9
10
11

分析：实参的array传参之后，形参的array会在栈上开辟不同与实参array的空间，但两者指向的是同一个堆上的对象。（数组传参的2种情况）
运行结果：

3. 奇数位于偶数之前
   调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
   如数组：[1,2,3,4,5,6]，调整后可能是：[1, 5, 3, 4, 2, 6]
   方法1：新创建一个数组对象存储

    public static int[] fun(int[] array) {
        int[] ret = new int[array.length];
        int j = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1){
                ret[j] = array[i];
                j++;
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0){
                ret[j] = array[i];
                j++;
            }
        }
        return ret;
    }
    public static void main(String[] args) {
        //奇数位于偶数之前
        int[] array = {1,2,3,4,5,6};
        int[] ret = fun(array);
        System.out.println(Arrays.toString(ret));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

分析：在fun方法内，定义一个新的数组对象，传入原数组对象，首先在原数组种筛选奇数加入到新数组中，然后筛选出偶数加入到新数组中，最后返回新数组并且打印输出。

方法2：在原数组对象上修改
分析：虽然方法1实现了奇数排在偶数之前，但是没有意义不太好，可以在记录数组首尾位置，然后首尾分别开始遍历数组，记录首不是奇数的位置，尾不是偶数的位置，然后交换这2个位置的元素值，注意条件是left小于right。

    public static void fun111(int[] array) {
        int left = 0;
        int right = array.length - 1;
        int tmp = 0;
        //期望在数组本身进行操作
        while (left < right) {
            while (left < right && array[left] % 2 != 0) {
                left++;
            }
            while (left < right && array[right] % 2 == 0) {
                right--;
            }
            tmp = array[left];
            array[left] =array[right];
            array[right] =tmp;
        }
    }
    public static void main(String[] args) {
        //奇数在偶数之前
        int[] array = {1,2,3,4,5,6};
        fun111(array);
        System.out.println(Arrays.toString(array));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果：

4. 查找数组中指定元素（顺序查找）
   给定一个数组，再给定一个元素，实现find方法找出该元素再数组中的位置。

    public static int find(int[] array, int n){
        for (int i = 0; i < array.length; i++) {
            if (n == array[i]) {
                return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        //查找数组中指定元素（顺序查找）
        int[] array = {1,2,3,4};
        int pos = find(array,3);
        System.out.println(pos);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

分析：找到返回下标位置，没有找到返回-1，因为数组没有-1下标，所有没有找到就返回-1。值为3的元素在数组中下表为2，故返回2。

5. 查找数组中指定元素（二分查找）
   给定一个有序整型数组, 实现二分查找

    public static int binFind(int[] array, int k) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] == k) {
                return mid;
            }else if (array[mid] > k) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        //二分查找
        int[] array = {1,2,3,4,5,6,7,8};
        int pos = binFind(array,10);
        System.out.println(pos);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果：

思想：先取中间位置的元素，然后使用带查找元素与数组中间元素进行比较：
①如果相等，即找到了返回该元素在数组中的下标
②如果小于，以类似方式到数组左半侧查找
③如果大于，以类似方式到数组右半侧查找
随着数组元素个数越多，二分的优势越大。

二分查找也可以直接调用Arrays中的binaryFind方法

    public static void main(String[] args) {
        int[] arry = {1,2,3,4,5,6,7};
        int k = Arrays.binarySearch(arry,5);
        System.out.println(k);
    }
1
2
3
4
5

运行结果：

如果没有找到，则返回一个负数，-本应该在的位置，eg，想要找8，8本应该在7之后，是第8个数，所有返回-8。

6. 冒泡排序
   给定一个整型数组, 实现冒泡排序(升序排序)

    public static void sort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) { //趟数
            for (int j = 0; j < array.length - i - 1; j++) { //比较次数
                if (array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }
    public static void main(String[] args) {
        //冒泡排序
        int[] array = {1,3,5,2,4,6};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行结果：

思想：
①将数组中相邻元素从前往后依次进行比较，如果前一个元素比后一个元素大，则交换，一趟下来最大的元素就在数组的末尾
②重复执行上述过程，直到数组中所有的元素都排列好。
冒泡排序性能比较低，Java中内置了更高效的排序算法，Array.sort

    public static void main(String[] args) {
        int[] arry = {1,21,13,46,5,6,7};
        Arrays.sort(arry);
        System.out.println(Arrays.toString(arry));
    }
1
2
3
4
5

运行结果：

进一步改进冒泡排序：
某一趟没有发生元素交换—>认为该数组已经有序了。
因此可以设置布尔类型的标志变量flag，判断是否哪一趟没有发生元素交换。【即下一趟元素没有发生交换，说明前一趟的排序已经让数组元素有序了】

        for (int i = 0; i < array.length - 1; i++) { //趟数
            boolean flag = false;
            for (int j = 0; j < array.length - i - 1; j++) { //比较次数
                if (array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = true;
                }
            }
            if (flag == false) {
                return;
            }
        }
    }
    public static void main(String[] args) {
        //冒泡排序
        int[] array = {1,3,5,2,4,6};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果：

System.currentTimeMillis() 获取时间，分析优化的算法

    public static void sort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) { //趟数
            boolean flag = false;
            for (int j = 0; j < array.length - i - 1; j++) { //比较次数
                if (array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = true;
                }
            }
            if (flag == false) {
                return;
            }
        }
    }
    public static void sort2(int[] array) {
        for (int i = 0; i < array.length - 1; i++) { //趟数
//            boolean flag = false;
            for (int j = 0; j < array.length - i - 1; j++) { //比较次数
                if (array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
//                    flag = true;
                }
            }
//            if (flag == false) {
//                return;
//            }
        }
    }
    public static void main(String[] args) {
        //冒泡排序
        int[] array = new int[100000];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis(); //取当前系统的时间
        sort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);

        long start2 = System.currentTimeMillis(); //取当前系统的时间
        sort2(array);
        long end2 = System.currentTimeMillis();
        System.out.println(end2 - start2);

    }
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

运行结果：（单位是毫秒）

7. 两数之和
   给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
   示例 1：
   输入：nums = [2,7,11,15], target = 9
   输出：[0,1]
   解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

    public static int[] findIndex(int[] array, int n){
        int[] ret = {-1,-1};
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if(array[i] + array [j] == n){
                    ret[0] = i;
                    ret[1] = j;
                    return ret;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] array = {2,7,11,15};
        int n = 9;
        int[] index = findIndex(array,n);
        System.out.println(Arrays.toString(index));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

分析：注意双重循环，第二重是从i+1开始，因为数字不能重复。
运行结果：

8. 存在连续三个奇数的数组
   给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。
   示例 1：
   输入：arr = [2,6,4,1]
   输出：false
   解释：不存在连续三个元素都是奇数的情况。
   示例 2：
   输入：arr = [1,2,34,3,4,5,7,23,12]
   输出：true
   解释：存在连续三个元素都是奇数的情况，即 [5,7,23] 。

    public static boolean findJi(int[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                count++;
                if (count == 3){
                    return true;
                }
            }else {
                count = 0;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        int[] array = {1,2,34,3,4,5,7,23,12};
        boolean b = findJi(array);
        System.out.println(b);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运行结果：

9. 只出现一次的数字
   给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
   示例 1: 输入: [2,2,1] 输出: 1
   示例 2:输入: [4,1,2,1,2] 输出: 4

    public static int findOnce(int[] array) {
        int ret = 0;
        for (int x: array) {
            ret ^= x;
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] array = {2,2,1};
        int ret = findOnce(array);
        System.out.println(ret);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

分析：异或，2个相同的数异或等于0，0和任何数异或等于那个数本身。
因为数组中只有一个数字出现一次，则其他出现2次的数字异或之后都是0，最终整个数字异或之后的结果就是所要找的元素值。
运行结果：

10. 多数元素
    给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
    你可以假设数组是非空的，并且给定的数组总是存在多数元素。
    示例 1：
    输入：[3,2,3]
    输出：3
    示例 2：
    输入：[2,2,1,1,1,2,2]
    输出：2
    方法1：排序之后，找中位数

    public static int findMore(int[] array) {
        Arrays.sort(array);
        //数组中出现次数超过一半的数字，一定是排好序之后的中间位置数字
        return array[array.length/2];
    }
    public static void main(String[] args) {
        int[] array = {2,2,1,1,1,2,2};
        int ret = findMore(array);
        System.out.println(ret);
    }
1
2
3
4
5
6
7
8
9
10

分析： 数组中出现次数超过一半的数字，一定是排好序之后的中间位置数字， 将数组排序后，数组n/2的元素一定是众数
运行结果：

方法2：类比投票的思想，一个tmp记录人名（元素值），一个count记录票数（次数），抵消的思想，比如A和B两个人被选举，投A的那1票，可以用投B的那一票抵消掉。

    public static int func(int[] array) {
        int tmp = array[0];
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == tmp) {
                count++;
            }else {
                count--;
            }
            if (count == 0) {
                tmp = array[i];
                count++;
            }
        }
        return tmp;
    }
    public static void main(String[] args) {
        int[] array = {1,1,3,34,2,4,5,6,7,7,8,7};
        int ret = func(array);
        System.out.println(ret);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果：

11. 数组逆序

    public static void reverse(int[] array) {
        int tmp = 0;
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            tmp = array[left];
            array[left] = array[right];
            array[right] =tmp;
            left++;
            right--;
        }
    }
    public static void main(String[] args) {
        //数组的逆序
        int[] array = {1,2,3,4};
        reverse(array);
        System.out.println(Arrays.toString(array));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

运行结果：

分析：设定两个下标，分别指向第一个元素和最后一个元素，交换2个位置的元素，让前一个下标自增，后一个下表自减，while循环。