数组基操三连（4）

不念不忘少年蓝@ 2022-01-23 05:43 142阅读 0赞

# 题目一 #

给定一个长度为N的整型数组arr，其中有N个互不相等的自然数1~N

请实现arr的排序

但是不要把下标0~N-1位置上的数值通过直接赋值的方式替换成1~N。

要求：时间复杂度为O(N)，额外空间复杂度为O(1)。

思路：从左向右检查，检查到需要换的以后，就直接把它放到该去的位置，然后被换掉的数，位置肯定也不对，继续重复相同的方法，最后肯定会跳回来（原因懒得说了自己想想），然后继续往下检查即可。

public static void sort1(int[] arr) {
    		int tmp = 0;
    		int next = 0;
    		for (int i = 0; i != arr.length; i++) {
    			tmp = arr[i];
    			while (arr[i] != i + 1) {
    				next = arr[tmp - 1];
    				arr[tmp - 1] = tmp;
    				tmp = next;
    			}
    		}
    	}

# 题目二 #

![70][]

本题一般思路：依次查找找到比前后都小的数；或者选出最小数，他肯定是局部最小的；等等

但这些都是O(n)的方法，而用二分可以做到O(logn).

二分思路：

考虑最左和最右的元素：如果arr\[0\]<arr\[1\] return 0; arr\[N-1\]<arr\[N-2\] return N-1;

考虑最中间元素，如果中间元素大于它左边的元素，那么局部最小值就应该在数组的左半部分

如果中间元素小于大于它右边的元素，那么局部最小值就应该在数组的右半部分

中间元素既小于它左边的值又小于它右边的值，那么它就是局部最小

# 题目三 #

给定一个整数数组arr，返回不包含本位置的累乘数组。

比如2 3 1 4返回12 8 24 6

方法一：算出所有数的乘积，每个位置除以自己即可。要注意坑：如果数组中有一个0，那么0这个位置就是其他数的乘积，其他位置全为0；如果有多个0，那么所有位置都是0.

public int[] product1(int[] arr) {
    		if(arr==null || arr.length<2) {
    			return null;
    		}
    		int count=0;//0的个数
    		int all=1;//除0以外的数的乘积
    		for(int i=0;i!=arr.length;i++) {
    			if(arr[i]!=0) {
    				all*=arr[i];
    			}else {
    				count++;
    			}
    		}
    		int[] res=new int[arr.length];
    		if(count==0) {
    			for(int i=0;i!=arr.length;i++) {
    				res[i]=all/res[i];
    			}
    		}else if(count==1) {
    			for(int i=0;i!=arr.length;i++) {
    				if(arr[i]==0) {
    					res[i]=all;
    				}
    			}
    		}
    		return res;
    	}

[70]: /images/20220123/e590b6c568ee43d59e9fa2290bbd7fed.png