数组相关算法题

寻找最小的k个数

输入n个整数，输出其中最小的k个。

思路：

1. 利用快排的思想，寻找第k个位置上正确的数，k位置前面的数即是比k位置小的数组，k后面的数即是比k位置元素大的数组。
2. 利用堆排序，特别适用于海量数据中寻找最大或者最小的k个数字。即构建一个大堆容器，初始化大小为k，变量初始数，如初始数组大小小于等于k直接返回，如果大于k，则选择数组的前k个元素，填充堆，然后调整为最大堆。调整完之后，继续从初始数组中拿出一个元素，如果该元素比大堆的堆顶小，则替换堆顶，继续调整为最大堆，如果大于等于堆顶则直接丢弃，不作调整。

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (input==null||input.length==0||input.length<k||k<=0) {
            return res;
        }
        int start  = 0;
        int end = input.length-1;
        int index = partition(input, start, end);
        //一直循环知道找到第k个位置正确的数。
        while (index != k - 1) {
            if (index > k - 1) {
                end = index-1;
                index = partition(input, start, end);
            } else {
                start = index+1;
                index = partition(input, start, end);
            }
        }
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }

   static int partition(int input[], int start, int end) {
        int tmp = input[start];
        while (start < end) {
            while (start < end && input[end] >= tmp) {
                end--;
            }
            input[start] = input[end];
            while (start < end && tmp >= input[start]) {
                start++;
            }
            input[end] = input[start];
        }
        input[start] = tmp;
        return start;
    }

数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

思路：

1. 数组中的数字为0到n-1的范围内。如果这个数组中没有重复的数字，则对应的i位置的数据也为i
2. 使用额外的空间，判断i位置数是否存在额外空间中

public Integer duplicate(int[] numbers) {
    if(numbers.length = 0 || numbers == null) return -1;
    int length = numbers.length;
    ArrayList list = new ArrayList();
    for(int i = 0;i<length;i++){
        if(list.contains(numbers[i]) return numbers[i]
        else list.add(numbers[i]);
    }
    return -1;
}

构建乘积数组

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。

思路：用矩阵的方式，先计算左下三角，再计算右上三角。根据图来分析即可。

public class MultiArray {
	// 新建一个新数组B， 对A数组i项左侧自上往下累乘，
	// 对A数组i项右侧自下往上累乘 时间复杂度O(n)
    public int[] multiply(int[] A) {
    	// 将B拆分为A[0] *...* A[i-1]和A[n-1]*...*A[i+1] 两部分
    	if(A == null || A.length ==0)
        	return A;
        int length = A.length;
        int [] B = new int[length];
        B[0] = 1;
        // 先计算左下三角形，此时B[0]只有一个元素，舍为1，
     	// B[0]不包括A[0]
        for (int i = 1; i < length; i++) {
			B[i] = B[i-1]*A[i-1];
		}
        int tmp =1;
        //计算右上三角形
        for (int i = length -1; i >=0; i--) {
			//最终的B[i]是之前乘好的再乘以右边的
        	B[i] *=tmp;
		tmp *= A[i];
		}
        
        return B;
    }
}

和为S的两个数

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

按奇偶排序数组

给定一个非负整数数组 A，返回一个由 A 的所有偶数元素组成的数组，后面跟 A 的所有奇数元素。

public int[] sortArrayByParity(int[] A) {
    int lo = 0;
    int hi = A.length -1;
    while(lo < hi){
        while(A[lo] % 2 == 0){
            if(lo == hi) break;
            lo++;
        } 
        while(A[hi] % 2 != 0){
            if(hi == lo) break;
            hi--;
        }
        if(lo > hi) break;
        int temp = A[lo];
        A[lo] = A[hi];
        A[hi] = temp;
    }    
}

连续子数组的最大和

算法时间复杂度O（n） 用total记录累计值，maxSum记录和最大
基于思想：对于一个数A，若是A的左边累计数非负，那么加上A能使得值不小于A，认为累计值对 整体和是有贡献的。如果前几项累计值负数，则认为有害于总和，total记录当前值。 此时 若和大于maxSum 则用maxSum记录下来

public class Solution {
	public int FindGreatestSumOfSubArray(int[] array) {  
		if(array.length == 0)
			return 0;
		int total = array[0];//当前的前面的和累计
		int maxsum = array[0];//记录可能的最大值
		for (int i = 1; i < array.length; i++) {
			if(total >= 0)
				total = total + array[i];
			else
				total = array[i];
			if(total > maxsum)
				maxsum = total;
		}
		return maxsum;
	}
}

把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路：
考虑到大数问题，先将整型数组转换成String数组，然后将String数组排序，最后将排好序的字符串数组拼接出来。关键就是制定排序规则。
排序规则如下： 若ab > ba 则 a > b， 若ab < ba 则 a < b， 若ab = ba 则 a = b；
解释说明： 比如 “3” < "31"但是 “331” > “313”，所以要将二者拼接起来进行比较

public String PrintMinNumber(int [] numbers) {
    if(numbers == null || numbers.length == 0)
        return "";
    int len = numbers.length;
    String[] str = new String[len];
    StringBuffer sb = new StringBuffer();
    //将数字型的放在字符串数组中。
    for (int i = 0; i < len; i++) {
	    str[i] = String.valueOf(numbers[i]);
	}
    //根据定义的规则重新堆str进行升序排序
    Arrays.sort(str, new Comparator<String>() {
		@Override
		public int compare(String s1, String s2) {
			String c1 = s1 + s2;
			String c2 = s2 + s1;
			return c1.compareTo(c2);
		}
 
	});
    //根据规则排好序，将结果依次放入stringbuffer中就行了
    for (int i = 0; i < len; i++) {
		sb.append(str[i]);
	}       
    return sb.toString();
}

和为S的连续正数序列

1. n = 2k + 1时，n项连续正数序列的和为S的条件: n & 1 && S / n == 0 解读 逻辑与的左边要求n为奇数，右边要求整个序列的平均数恰好为中间数。
2. n = 2k时，n项连续正数序列的和为S的条件： S % n * 2 == n 解读 S % n 的结果是中间两项左边的那项，乘2刚好是项数。举例，现有S = 39,6个连续正数序列和式能不能为S呢？套用公式，39 % 6 * 2 =6 == 6，我们也知道，这次的序列是 4、5、6、7、8、9，取余的结果为3对应着值为6的那一项，也就是中间项左边的那一项。
3. 和为S，项数为n，如何写出这个序列？ S / n - (n-1) / 2 解读 执行的除法是地板除法（floor），不管最终结果有无小数都直接舍去。仍使用上述例子，39 / 6 = 6，6恰好是中间项左边的那一项，6 - （6-1）/ 2 = 4，恰好是序列最左端。序列写出来就没问题。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
 
        vector<vector<int> > allRes;
        for (int n = sqrt(2 * sum); n >= 2; --n) {
            if (((n & 1) == 1 && sum % n == 0) || (sum % n * 2 == n)){
                vector<int> res;
                //j用于计数，k用于遍历求值
                for(int j = 0,k = sum / n - (n - 1) / 2; j < n; j++, k++)
                    res.push_back(k);
                allRes.push_back(res);
            }  
        }
        return allRes;
    }
};

还有一点需要注意，S = （a0 + a0 +n-1）* n / 2，等差序列公式自然是不必说的。对其进行放缩，就有S > n平方 / 2；即n < 根号2S（这一点在解法4中也有涉及）。这样做的话可以减少遍历次数。 在for循环中就有体现。

for (int n = sqrt(2 * sum); n >= 2; --n)

时间复杂度为O(根号sum )。

数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。