[数据结构与算法]数组的常用操作及方法

一.数组的表示：

int[] arr={1,8,16,9};//方法一
int[] arr=new int[]{1,8,16,9};//方法二
int[] arr=new int[4];//方法三
arr[0]=1;
arr[1]=8；
arr[2]=16;
arr[3]=9;

?二.数组中常见问题

1.求数组中最小值

方法一：

public class exercise {
    public static void main(String[] args) {
        int[] arr = {8, 5, 50, 15, 6, 22, 19};
        System.out.println("数组中最小值是" + minNum(arr));

    }

    public static int minNum(int[] arr) {
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        return min;

    }
}

方法二：

public class exercise {
    public static void main(String[] args) {
        int[] arr = {8, 5, 50, 15, 6, 22, 19};
        System.out.println("数组中最小值是"+minNum(arr));
    }
    public static int minNum(int[]arr)
    {
        Arrays.sort(arr);//快速排序
        return arr[0];
    }
}

2.数组拷贝

import java.util.Arrays;
public class exercise {
    public static void main(String[] args) {
        int[] arr=new int[]{1,5,8,9,11,16};
        int[] arr2=Arrays.copyOf(arr,arr.length);//拷贝了arr数组;
        for (int i:arr) {
            System.out.print(i+" ");
        }
        System.out.println();
        for (int i:arr2) {
            System.out.print(i+" ");

        }
        for
        System.out.println();
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr2));
    }
}

输出结果为：

可见输出arr数组有两种方法，一种是使用foreach遍历数组，另一种是使用Arrays.toString。Java提供了一个类，通过调用该工具类的方法即可完成对数组的操作。这个类就是Arrays，它保存在java.util包中，提供多种操作数组的方法。我们这里的Arrays.toString就是将数组转化为字符串。

3.求数组的平均值

public class exercise {
    public static void main(String[] args) {
        int[] arr={1,5,8,12};
        System.out.println(avg(arr));
    }
    public static double avg(int[] arr)
    {
        double sum=0;
        for (int i:arr) {
            sum+=i;
        }
        return sum/arr.length;
    }
}

?4.改变数组的值

public class exercise {
    public static void main(String[] args) {
        int[] arr={1,2,3};
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(transform(arr)));

    }
    public static int[] transform(int[]arr)
    {
        int[] arr2=new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr2[i]=arr[i]*2;
        }
        return arr2;
    }
}

输出结果：

?5.多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ? n/2 ? 的元素。假设数组是非空的，并且给定的数组总是存在多数元素。

思路：出现的次数大于n/2,将一个数组排序后，中位数一定是它的众数，即多次出现的元素

public class exercise {
    public static void main(String[] args) {
        int[] arr={5,2,5,5,2};
        System.out.println(manyNum(arr));

    }
    public static int manyNum(int[] arr)
    {
        Arrays.sort(arr);
        return arr[arr.length/2];
    }
}

6.二分查找

方法一：

import java.util.Arrays;

public class exercise {
    public static void main(String[] args) {
        int[] arr = {5, 1, 6, 8, 9, 2, 45};
        System.out.println(binarySearch(arr, 1));

    }

    public static int binarySearch(int[] arr, int tofind) {
       int left=0;
       int right=arr.length-1;
        Arrays.sort(arr);
        while (left <= right) {
          int mid = (left + right) >> 1;
            if (arr[mid] == tofind) {
                return mid;
            } else if (arr[mid] > tofind) {
                right = mid - 1;
            } else {
                left = mid + 1;

            }

        }
       return -1;
    }
}

方法二：

import java.util.Arrays;
public class exercise {
    public static void main(String[] args) {
        int[] arr = {5, 1, 6, 8, 9, 2, 45};
      System.out.println(binarySearch(arr, 2, arr.length-1,0));
    }
    public static int binarySearch(int[] arr,int tofind,int right,int left)
    {
        Arrays.sort(arr);
        int mid=(right+left)>>1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[mid]==tofind)
            {
                return mid;
            }
            else if (arr[mid]>tofind)
            {
                return binarySearch(arr,tofind,right-1,left);
            }
            else
            {
              return binarySearch(arr, tofind, right, left+1);
            }
        }
        return -1;
    }
}

7.整数求逆

import java.util.Arrays;

public class exercise {
    public static void main(String[] args) {
        int[] arr={1,2,3,4};
        System.out.println(Arrays.toString(reverse(arr)));
    }
    public static int[] reverse(int[] arr)
    {
        int right= arr.length-1;
        int left=0;
        while (left<right)
        {
            int tmp=arr[left];
            arr[left]=arr[right];
            arr[right]=tmp;
            left++;
            right--;
        }

        return arr;
    }
}

8.冒泡排序

import java.util.Arrays;

public class exercise {
    public static void main(String[] args) {
        int[] arr={1,5,3,7,12,6};
        System.out.println(Arrays.toString(bubbleSort(arr)));

    }
    public static int[] bubbleSort(int[]arr)
    {
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-i-1; j++)
            {
                if (arr[j]>arr[j+1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        return arr;

    }

}