Tag: 算法

看了LeetCode上牛人的解答，感觉我的智商被碾压了~

原题

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
给定一个包含n+1个整数的数组nums，该数组中的每个整数都在[1,n]的范围内，假设数组中只有一个数是重复的，找到那个重复的数。
Note|提示:

1. You must not modify the array (assume the array is read only).|    不能改动数组内容
2. You must use only constant, O(1) extra space.|    在O(1)的空间复杂度内完成
3. Your runtime complexity should be less than O(n2).|    时间复杂度不超过O(n^2)
4. There is only one duplicate number in the array, but it could be repeated more than once.|    只有一个重复数字，但是可能重复超过一次

思路1：O(nlogn)时间复杂度

英文版解释：https://leetcode.com/discuss/60830/solutions-explanation-space-without-changing-input-array
这个解法涉及到鸽巢原理。
假设有n=10的一个数组（大小是n+1），那我目前的搜索范围是[1,10]，先找中间的数mid=5.现在我们遍历数组的所有元素并统计<=5的元素个数，记作n_lteq5好了，那么有：

• 如果n_lteq5>5，那就有6个数字占了本来只有5个的坑位，那目标数字肯定是在[1,5]的范围内了；
• 如果n_lteq5<=5，那前面的元素都挺守规矩的，得看看[6,10]里头哪个数字在作怪；

这样每一次判断，问题的规模都会缩小一半，一共n+1个数字，时间复杂度是O(nlogn)
感觉碰到了很多二分思想的题目啊，关键点就是要找到一个什么划分方式把问题的规模缩小掉，而在这道题里头用到的就是鸽巢原理。

思路1代码

class Solution {
public:
    int countLtEq(const vector<int>& nums, int n){
        int count = 0;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] <= n)
                count ++;
        }
        return count;
    }
    int findDuplicate(vector<int>& nums) {
        int n = nums.size() - 1;
        int min = 1, max = n;
        int mid;
        int ltEqCnt;
        while(min < max){
            mid = (min + max)/2;
            ltEqCnt = countLtEq(nums, mid);
            if(ltEqCnt <= mid){
                //[min, mid]是正常的，找另一边
                min = mid+1;
            } else {
                max = mid;
            }
        }
        return min; // min == max
    }
};

插曲：如果可以改变数组元素呢？

感觉在剑指Offer上遇到过类似的题目。如果可以改变数组元素的话，可以按照下面的思路进行，时间复杂度是O(n)。基本思想是，一个萝卜一个坑，把搜索到的数放到自己应该在的位置上，比如1应该放在第一个位置上，如果后面再找到一个1，我们就会发现1这个位置的坑被前一个1占了，那就冲突了。
方便起见，数组的位置按1,2,3,…描述（而非0,1,2…）。假设有数组[5,4,2,3,1,5,6] ，当前工作的位置pos=1

• 先看第pos=1个数字5，在设想的排好序的序列里，5应该就在第5个位置上，因此我们把5和第5个位置上现有的数字1进行调换，结果就变成了[1,4,2,3,5,5,6] ；
• 看换回来的数字1，由于已经在1号位上，这次处理就结束了，往前挪一下，pos=2，看下一个数字；
• pos=2的数字是4，本来应该在4号位上，因此把4和4号位上的 3调换，数组变成[1,3,2,4,5,5,6] ；
• 这时候事情没完，因为换回来的3不在应该有的3号位上，因此把3和3号位上占着的2调换，数组变成[1,2,3,4,5,5,6] ；
• 换回的数字2是正确的位置，因此pos++，变成pos=3，类似地检查pos=4, 5发现都符合要求；
• 当pos=6时，此时位置上的元素是5，于是我们想把这个5归为到5号位，但是检查5号位的时候我们发现，上面已经有一个5了，这就说明5是重复数值了，搞定

可能有问，那如果原来的数组是[5,4,2,3,1,6,5] 呢？很显然，如果前面找到pos=6的时候都没发生冲突，那罪魁祸首肯定在最后个元素上面了。
这种方法只要遍历一次数组并做相应替换就行，除了会改变数组内容外，其他条件都满足，可惜啊。

思路2：O(n)时间复杂度

大神，大家快去膜拜：http://keithschwarz.com/interesting/code/?dir=find-duplicate
据说越是经典的代码行数越是写的简单，然而你并不能看懂…
似乎是把数组中的值看做单链表的next指针的值的，还在理解中~这个算法理论上是正确的。
 

题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/
参考文献：

• 求两个有序数组的中位数-算法导论
• 求两个有序数组的中位数或者第k小元素

思路：
实在是脑子转不过来，看了一下解法，然后就把自己的理解讲一下吧。
有两个规律需要说下：
1.在某个数列头尾删去相同数量的元素，其中位数是不变的。比如[1,2,3,4]删去1和4.
2.如果两个数列的中位数是m1, m2，那么合并后的数列的中位数的值肯定在[m1,m2]范围内。
既然题目是要Log级别的复杂度，就要想到要用折半法把问题的规模降低…举个例子，假设有[1,2,4,6,6,8]和[1,5,7,8,10,25,36]两个数列，很容易算出他们的（前序 ）中位数分别是4和8，而他们合并后的中位数的值在[4,8]之间。
然后可以删去无用的值，[1,2]与[10,25,36]. 但由于规律1的限制，如果后面删了3个的话，合并后删减的数列会发生变化（本例中奇偶性都变了），我们只能删去min(2,3)=2个元素…这种删值从理论上讲就是折半了，然后搞一波递归就行了。
最最最基本的思路如下：

两个有序数列Ary1, Ary2（假设升序排列）的中位数分别为m1,m2
if m1 == m2:
    LUCKY!!!
elif m1 < m2:
    取（Ary1的后半段，Ary2的前半段）再算
else
    取（Ary1的前半段，Ary2的后半段）再算

由于题设里面俩数组是不等长的，所以里对其中某个数组n<=2时处理方法需要注意…
代码：

int max(int x, int y) {
    return x>y ? x : y;
}
int min(int x, int y) {
    return x<y ? x : y;
}
double getMedian(int* nums, int size) {
	if (size == 0)
		return -1;
	if (size % 2 == 0) {
		//Even number
		return (nums[size / 2] + nums[size / 2 - 1]) / 2.0;
	}
	else {
		return nums[(size - 1) / 2];
	}
}
double findMedianMerge(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int count = 0;
	int n1Count = 0;
	int totalSize = nums1Size + nums2Size;
	int t1, t2;
	if (totalSize % 2 == 0) {
		t1 = totalSize / 2;
		t2 = t1 + 1;
	}
	else {
		t1 = -1;
		t2 = totalSize / 2 + 1;
	}
	double sum = 0;
	int curVal;
	while (n1Count < nums1Size) {
		if (*nums1 < *nums2) {
			n1Count++;
			curVal = *nums1;
			nums1++;
		}
		else {
			curVal = *nums2;
			nums2++;
		}
		count++;
		if (count == t1 || count == t2) {
			sum += curVal;
		}
		else if (count >= t2) {
			break;
		}
	}
	if (count < t1) {
		//Not finished
		nums2 += (t1 - count - 1);
		count = t1;
		sum += *nums2;
		nums2++;
	}
	if (count < t2) {
		nums2 += (t2 - count - 1);
		sum += *nums2;
	}
	if (t1 == -1)
		return sum;
	else
		return sum / 2.0;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int totalSize = nums1Size + nums2Size;
	if (nums1Size > nums2Size) {
		//Keep ary1 shorter than ary2
		int* temp = nums1;
		int t = nums1Size;
		nums1 = nums2;
		nums1Size = nums2Size;
		nums2 = temp;
		nums2Size = t;
	}
	if (nums1Size == 0) {
		return getMedian(nums2, nums2Size);
	} else if (nums1Size == 1) {
		if (nums2Size == 1) {
			return (nums1[0] + nums2[0]) / 2.0;
		}
		else {
			return findMedianMerge(nums1, nums1Size, nums2, nums2Size);
		}
	}
	else if (nums1Size == 2) {
		if (nums2Size == 2) {
			return (max(nums1[0], nums2[0]) + min(nums1[1], nums2[1])) / 2.0;
		}
		else {
			return findMedianMerge(nums1, nums1Size, nums2, nums2Size);
		}
	}
	//Slice
	double m1 = getMedian(nums1, nums1Size);
	double m2 = getMedian(nums2, nums2Size);
	if (m1 == m2) {
		//Got lucky
		return m1;
	}
	else if (m1 < m2) {
		//Slice L-nums1 and R-nums2
		int cut = (nums1Size - 1) / 2;
		return findMedianSortedArrays(nums1 + cut, nums1Size - cut, nums2, nums2Size - cut);
	}
	else {
		//Slice R-nums1 and L-nums2
		int cut = (nums1Size - 1) / 2;
		return findMedianSortedArrays(nums1, nums1Size - cut, nums2 + cut, nums2Size - cut);
	}
}