Leetcode Array 442,15 @Python－CONY的世界

442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

Success: 本來的做法update在github裡面，採用先sort在比對的方式，不過performance不好，所以跑去看論壇裡的解法

這題最快的人是用set寫，但是我覺得多開一個seen set這種做法應該不行，因為多用了extra space啊

自己實作論壇裡我認為可行的方法，發現一個有趣的現象，我理解後重寫成的版本(399 ms)，發現沒有原版本快，明明只差在< 和 >= ，不知道是不是跟access nums的行數有關係

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = [];
        for x in nums:
            if nums[abs(x)-1] < 0:
                result.append(abs(x))
            else:
                nums[abs(x)-1] *= -1
        return result

原版本(309 ms)

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ret = []
        for n in nums:
            if nums[abs(n) - 1] >= 0:
                nums[abs(n) - 1] *= -1
            else:
                ret.append(abs(n))
        return ret

Fail:

1. Time Limit Exceeded ，list.count() complexity O( nlogn )

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return list(set([x for x in nums if nums.count(x)>1]))

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Success: 官方解法

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        for index in range(len(nums)-2):
            if index > 0 and nums[index] == nums[index-1]: continue
            l,r = index+1, len(nums)-1
            while l < r:
                s = nums[index]+nums[l]+nums[r]
                if s > 0:
                    r-=1
                elif s < 0:
                    l+=1
                else:
                    result.append([nums[index], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l+1]:
                        l+=1
                    while l < r and nums[r] == nums[r-1]:
                        r -=1
                    l+=1
                    r-=1
        return result

概念可以看wiki 3sum (https://en.wikipedia.org/wiki/3SUM) 簡單概念範例圖大概是這樣，sort後固定一個值找剩下符合的差

 -25 -10 -7 -3 2 4 8 10  (a+b+c==-25)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-22)
 . . .
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-3)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==2)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==0)

3sum 是k sum 的其中一個例子，這種類型的題目有個固定的解法，看到Sigmanfy的c++例子是

vector< vector<int> > KSum(vector<int> &num, int K, int target, int p) {
		vector< vector<int> > vecResults;
		if (K == 2) { // base case
			vector<int> tuple(2, 0);
			int i = p, j = num.size() - 1;
			while (i < j) {
				if (i > p && num[i] == num[i - 1]) {
					++i;
					continue;
				}
				int sum = num[i] + num[j];
				if (sum == target) {
					tuple[0] = num[i++];
					tuple[1] = num[j--];
					vecResults.push_back(tuple);
				}
				else if (sum > target) {
					--j;
				}
				else {
					++i;
				}
			}
			return vecResults;
		}
		// K > 2
		for (int i = p; i < num.size(); ++i) {
			if (i > p && num[i] == num[i - 1]) continue;
			vector< vector<int> > K1Sum = KSum(num, K - 1, target - num[i], i + 1);
			for (auto it = K1Sum.begin(); it != K1Sum.end(); ++it) {
				vector<int> tuple;
				tuple.push_back(num[i]);
				tuple.insert(tuple.end(), it->begin(), it->end());
				vecResults.push_back(tuple);
			}
		}
		return vecResults;
	}

此類complexity 是O(N^(K-1))

Fail:

1. Time Limit Exceeded

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        once = []
        twice = []
        triple = []
        for x in nums:
            if x not in once:
                once.append(x)
            elif x not in twice:
                twice.append(x)
            elif x not in triple:
                triple.append(x)
        for x in range(len(once)-2):
            for y in range(x+1,len(once)-1):
                for z in range(y+1, len(once)):
                    if once[x]+once[y]+once[z] == 0:
                        result.append([once[x], once[y], once[z]])
        for x in twice:
            for y in once:
                if x != y and 2*x+y == 0:
                    result.append([x,x,y])
        for x in triple:
            if 3*x == 0:
                result.append([x,x,x])
        return result