Tag Archives: 排序

LeetCode Intersection of Two Arrays II

Leave a reply

LeetCode Intersection of Two Arrays II Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2]. Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.
Follow up:
  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
求两个数组的交集，这里的交集又不同之前LeetCode Intersection of Two Arrays的交集了，这里的交集不再满足集合的互异性，两个数组中有多个同一个数，有几个共有，交集里就有几个，看例子就知道了。 这其实简化了问题，我们对其中一个数组hash，建立数字和频率的hash表，然后遍历另一个数组，hash表中有，则加入交集，同时hash中的频率减1，也不需要对结果去重了。完整代码如下： [cpp] class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> hash; vector<int> ans; for (int i = 0; i < nums1.size(); ++i) { ++hash[nums1[i]]; } for (int i = 0; i < nums2.size(); ++i) { if (hash[nums2[i]]>0) { ans.push_back(nums2[i]); –hash[nums2[i]]; } } return ans; } }; [/cpp] 本代码提交AC，用时6MS。 回答一下Follow up的三个问题： 如果数组已排序，则可以用归并排序的思路求交集，两个指针i,j分别指向两个数组，然后判断nums[i]==nums[j]，如果相等，则加入交集，i,j都往后移；否则根据大小关系选择后移i或j。 不过我觉得代码中的Hash思路已经够快了，时间复杂度应该都是O(n1+n2)，只不过Hash毕竟需要计算Hash值，Hash占用的隐性空间也比较大，所以归并的思路可能会快一些。 如果nums1.size<nums2.size()，则归并的思路会快一些，因为归并的话，其实复杂度是O(min(n1,n2))，当一个数组的指针走到头之后，算法就结束了，而Hash的话，就必须走完两个数组。 如果nums2不能一次load进内存，则分批load内存查Hash。]]>

LeetCode Valid Anagram

Leave a reply

242. Valid Anagram 242. Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case? 242. Valid Anagram

“Anagram”这个词的意思是“易位构词游戏”，就是把一个word中的letter打乱。本题要判断两个字符串是否是anagram。简单题，直接对两个字符串hash，分别统计出现字符的频率，如果两个hash的结果完全一样，则是anagram；否则不是。 这题和LeetCode Word Pattern类似，也是要保证两个字符串hash到的频率完全一样，即是一个双射。完整代码如下：

class Solution {
public:
    bool isAnagram(string s, string t)
    {
        unordered_map<char, int> ums, umt;
        for (int i = 0; i < s.size(); ++i) {
            ++ums[s[i]];
        }
        for (int i = 0; i < t.size(); ++i) {
            ++umt[t[i]];
        }
        unordered_map<char, int>::iterator it = ums.begin();
        while (it != ums.end()) {
            if (umt[it->first] != it->second)
                return false;
            ++it;
        }
        it = umt.begin();
        while (it != umt.end()) {
            if (ums[it->first] != it->second)
                return false;
            ++it;
        }
        return true;
    }
};

本代码提交AC，用时16MS。
还有一种方法就是对两个字符串都排个序，然后判等，代码很简单，但是排序复杂度要比直接hash稍高。代码如下：

class Solution {
public:
    bool isAnagram(string s, string t)
    {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

本代码提交AC，用时26MS。

LeetCode Majority Element

1 Reply

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

要求出一个数组中的多数元素，这里的多数元素是指出现次数多于数组长度的一半。 很有意思的一个题目，前几天听旁边一个组的同学面试回来就说被问到了这个题。 常规思路是把数组排序，然后取⌊ n/2 ⌋这个元素，这种思路的算法复杂度为$O(nlgn)$的代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

本代码提交AC，用时52MS。
还有另一种巧妙的思路，假设一个数组是[1,1,2,2,1,1,3,1]，多数元素是1，如果从数组中同时删除元素1和2，剩余的数组[1,2,1,1,3,1]中，多数元素还是1。也就是说从数组中删除两个不同的元素，剩余数组中的多数元素和原数组中的多数元素是一样的。这种算法好像叫做摩尔投票法。
根据这种思路，我们定义两个变量ans和cnt，初始时cnt=0。当cnt==0时，此时是原始数组或者删除了两个不同的元素。以后每次，遇到和ans相同的元素，cnt++，否则cnt–。cnt–就相当于删掉两个不同的元素。
这种思路只需要遍历一遍原数组，时间复杂度是$O(n)$，完整代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        int ans, cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (cnt == 0) {
                ans = nums[i];
                cnt++;
            }
            else {
                if (nums[i] == ans)
                    cnt++;
                else
                    cnt–;
            }
        }
        return ans;
    }
};

本代码提交AC，用时22MS。果然比之前的快很多。

LeetCode Partition List

1 Reply

86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

本题要求把链表中小于某个数的节点移到大于等于某个数的节点前面，要求两个部分中的节点的相对顺序不变。 思路很简单，维护两个链表，一个是小于x的，另一个是大于等于x的，然后遍历原链表，分别把小于和大于等于x的节点接到对应的链表上。最后记得把第一个链表的尾部连到第二个链表的头部，然后第二个链表的尾节点置空。 完整代码如下：

class Solution {
public:
    ListNode* partition(ListNode* head, int x)
    {
        ListNode *head1 = new ListNode(0), *head2 = new ListNode(0);
        ListNode *prior1 = head1, *prior2 = head2;
        while (head != NULL) {
            if (head->val < x) {
                prior1->next = head;
                prior1 = prior1->next;
            }
            else {
                prior2->next = head;
                prior2 = prior2->next;
            }
            head = head->next;
        }
        prior2->next = NULL;
        prior1->next = head2->next;
        return head1->next;
    }
};

本代码提交AC，用时6MS。

LeetCode Remove Duplicates from Sorted Array II

Leave a reply

80. Remove Duplicates from Sorted Array II

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

这一题是LeetCode Remove Duplicates from Sorted Array的升级版，如果数组中的重复元素允许最多保留2个，又应该怎么处理呢。
可以通过修改LeetCode Remove Duplicates from Sorted Array的代码实现，添加一个cnt来统计重复出现的次数，如果小于3次，则i（最多不超过2次重复的最末尾的下标）的下标还是不停往前移，否则i暂停，但j还是要往前移。如果遇到不等的元素，则重置cnt=1。完整代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        if (nums.size() < 3)
            return nums.size();
        int i = 0, j = i + 1, cnt = 1;
        while (j < nums.size()) {
            if (nums[j] != nums[i]) {
                cnt = 1;
                nums[++i] = nums[j++];
            }
            else {
                cnt++;
                if (cnt < 3)
                    nums[++i] = nums[j++];
                else
                    j++;
            }
        }
        return i + 1;
    }
};

本代码提交AC，用时13MS。

上面的代码理解起来有点绕，网上有一种解法还是很好理解的，直接比较当前元素和前一个元素是否相等，相等则cnt++，否则cnt=1，同时如果cnt<3，则把最多重复2次的元素往前移。完整代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        if (nums.size() < 3)
            return nums.size();
        int cnt = 0, j = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i – 1]) {
                cnt++;
                if (cnt >= 3)
                    continue;
            }
            else {
                cnt = 1;
            }
            nums[j++] = nums[i];
        }
        return j;
    }
};

本代码提交AC，用时16MS。

二刷。双指针，i表示合法的填入位置，j一直往前走，如果和target相等，则填入i位置；否则更新target值。

class Solution {
public:
	int removeDuplicates(vector<int>& nums) {
		int n = nums.size();
		if (n == 0)return 0;
		int target_value = nums[0], target_id = 0;
		int i = 0, j = 0;
		while (j < n) {
			while (j < n&&nums[j] == target_value) {
				if (j < target_id + 2)nums[i++] = target_value;
				++j;
			}
			if (j < n) {
				target_id = j;
				target_value = nums[j];
			}
		}
		return i;
	}
};

本代码提交AC，用时16MS。

LeetCode Merge Sorted Array

Leave a reply

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

把两个已排序数组合并成一个有序数组。注意是保存到nums1中。我一开始理解的是在合并过程中不能借助额外空间，所以用两个指针i,j指向两个数组，然后每次从nums2中找第一个小于nums1[i]的数，然后交换nums1[i]和nums2[j]，再调整nums2使有序。如此下去，nums1就是合并有序数组中的较小数组部分。
这个版本的完整代码如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        if (n == 0)
            return;
        int i = 0;
        while (i < m) {
            int j = 0;
            while (nums1[i] <= nums2[j] && i < m)
                i++;
            if (i >= m)
                break;
            swap(nums1[i], nums2[j]);
            while (j < n – 1 && nums2[j] > nums2[j + 1]) {
                swap(nums2[j], nums2[j + 1]);
                j++;
            }
            i++;
        }
        for (int j = 0; j < n; j++) {
            nums1[i++] = nums2[j];
        }
    }
};

本代码提交AC，用时6MS。但是只击败了15%的人，仔细看看算法实现，最坏复杂度是$O(n*m)$，因为如果nums1={6,7,8,9,10}，nums2={1,2,3,4,5}，则nums1[i]每和nums2[0]交换一次，nums2调整时都要交换n-1次，所以最坏复杂度是$O(n*m)$。所以应该还有更好的算法。
看题解，发现我没有很好利用nums1的数组大小至少是n+m这个信息，这说明合并之后的整个数组，最大下标只能是n+m-1，所以我们可以对nums1和nums2从后往前比较，把更大的元素依次在nums1[n+m-1]往前放，这样共3个指针，他们之间不会有overlap。此算法的复杂度只有$O(max(n,m))$。

完整代码如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        if (n == 0)
            return;
        int i = m – 1, j = n – 1, k = m + n – 1;
        while (i >= 0 || j >= 0) {
            int a = i >= 0 ? nums1[i] : INT_MIN;
            int b = j >= 0 ? nums2[j] : INT_MIN;
            if (a > b) {
                nums1[k–] = a;
                i–;
            }
            else {
                nums1[k–] = b;
                j–;
            }
        }
    }
};

本代码提交AC，用时3MS，果然快多了。

LeetCode Sort Colors

Leave a reply

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?

这道题有意思。实质是要把由0,1,2组成的数组从小到大排序，本来用计数排序，分别统计一下0,1,2这3个数字各有多少个，然后重新构造一个排好序的数组即可，但是Follow up里提到不能使用two-pass算法，并且只能使用常数空间复杂度。 我稍加思考，想到一个可行的算法。因为数组中只有3个数字，那么排好序的数组开头肯定是0（如果有0的话），结尾肯定是2（如果有2的话）。所以我们只需一遍遍历，遇到0则放到开头，遇到2则放到结尾，遇到1的话，就先统计一下1的数目。最后把1重新赋值到所有0的后面，1的个数在前面已经统计过了，所以正好。 完整代码如下：

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int p0 = 0, p2 = nums.size() – 1; // p0和p2分别代表下一个0和2应该填入的位置
        int n1 = 0; // 1的数量
        for (int i = 0; i <= p2; i++) {
            if (nums[i] == 0)
                nums[p0++] = nums[i];
            else if (nums[i] == 1)
                n1++;
            else {
                swap(nums[i], nums[p2]);
                p2–;
                i–;
            }
        }
        for (int i = 0; i < n1; i++)
            nums[p0++] = 1;
    }
};

本代码提交AC，用时3MS。

二刷。看评论区的题解，代码如下，zero和second分别表示可以下一个可以放0或者2的位置。i不断往前扫描，遇到2把它放末尾，遇到0把它放开头，如此不断swap之后，1都被扔到中间了。i最多进行了一次扫描。

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int zero = 0, second = nums.size() - 1;
        int i = 0;
        while (i <= second) {
            while (i < second && nums[i] == 2) {
                swap(nums[i], nums[second--]);
            }
            while (i > zero && nums[i] == 0) {
                swap(nums[i], nums[zero++]);
            }
            ++i;
        }
    }
};

本代码提交AC，用时6MS。

LeetCode Remove Duplicates from Sorted Array

1 Reply

26. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

对一个已排序的数组，去掉其中的重复元素并返回新数组长度，相当于实现unique函数。多提一点，unique函数只去掉连续重复元素中的重复元素，并不保证unique之后的数组中没有重复元素，这点很重要，可以看cplusplus的例子，数组

10 20 20 20 30 30 20 20 10

unique之后的结果是

10 20 30 20 10 ?  ?  ?  ?

前面3个重复的20只取了一个，但是隔了两个30之后又出现了两次20，此时还是取了一个20，尽管前面已经出现过20了。所以为了实现对任意数组去重的目的，需要先sort再unique。
回到本题，思路很简单，初始化两个指针i,j，i指向不重复元素的最后一个下标，j遍历数组，如果nums[j]==nums[i]，说明重复，j++；否则把nums[j]放到nums[i+1]，i++。完整代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        if (nums.size() <= 1)
            return nums.size();
        int i = 0, j = i + 1;
        while (j < nums.size()) {
            if (nums[j] != nums[i]) {
                nums[i + 1] = nums[j];
                i++;
            }
            j++;
        }
        return i + 1;
    }
};

本代码提交AC，用时32MS。

LeetCode Merge k Sorted Lists

Leave a reply

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

归并k个已排序的链表。 之前是归并2个已排序的链表，现在变成多个了。其实就是多路归并，思路之前都知道，不同思路的区别就在于怎样找到所有链表当前位置的最小值，可以直接线性查找，也可以用败者树、胜者树或者堆。我一开始用线性查找，不出意外的TLE了，后来改用建堆的方法，顺利通过。 写代码越来越懒了，直接上STL，需要注意的是STL中的make_heap默认建的是大顶堆，我们需要传自己的比较函数进去以便构建小顶堆。

typedef struct Node {
    ListNode* ln;
    int idx;
    bool operator<(const Node& p) const { return this->ln->val < p.ln->val; }
    bool operator>(const Node& p) const { return this->ln->val > p.ln->val; }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        ListNode *ans = new ListNode(0), *head = ans;
        vector<Node> vn;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL) {
                Node nd;
                nd.ln = lists[i];
                nd.idx = i;
                vn.push_back(nd);
                lists[i] = lists[i]->next;
            }
        }
        if (vn.size() == 0)
            return NULL;
        make_heap(vn.begin(), vn.end(), greater<Node>());
        while (true) {
            Node tmp = vn.front();
            ans->next = tmp.ln;
            ans = ans->next;
            pop_heap(vn.begin(), vn.end(), greater<Node>());
            vn.pop_back();
            if (lists[tmp.idx] != NULL) {
                tmp.ln = lists[tmp.idx];
                vn.push_back(tmp);
                push_heap(vn.begin(), vn.end(), greater<Node>());
                lists[tmp.idx] = lists[tmp.idx]->next;
            }
            if (vn.empty())
                break;
        }
        return head->next;
    }
};

本代码提交AC，用时420MS。

二刷。更简单的是直接使用STL的优先队列，代码如下：

struct LNNode {
	ListNode* ln;
	LNNode() :ln(NULL) {};
	bool operator<(const LNNode& ln_) const{ // 注意两个const都不能少
		return ln->val > ln_.ln->val;
	}
};
class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<LNNode> pq;
		for (int i = 0; i < lists.size(); ++i) {
			if (lists[i] != NULL) {
				LNNode cur;
				cur.ln = lists[i];
				pq.push(cur);
			}
		}
		ListNode* root = new ListNode(0);
		ListNode* ans = root;
		while (!pq.empty()) {
			LNNode cur = pq.top();
			pq.pop();
			root->next = cur.ln;
			root = root->next;
			if (cur.ln->next) {
				LNNode nxt;
				nxt.ln = cur.ln->next;
				pq.push(nxt);
			}
		}
		return ans->next;
	}
};

本代码提交AC，用时32MS。

或者不用定义新的类，直接用原来的ListNode*，但新增一个比较函数，代码如下：

struct cmp {
	bool operator()(ListNode* l1, ListNode* l2) {
		return l1->val > l2->val;
	}
};

class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
		for (int i = 0; i < lists.size(); ++i) {
			if (lists[i] != NULL) {
				pq.push(lists[i]);
			}
		}
		ListNode* root = new ListNode(0);
		ListNode* ans = root;
		while (!pq.empty()) {
			ListNode* cur = pq.top();
			pq.pop();
			root->next = cur;
			root = root->next;
			if (cur->next) {
				pq.push(cur->next);
			}
		}
		return ans->next;
	}
};

本代码提交AC，用时32MS。

LeetCode Merge Two Sorted Lists

1 Reply

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

归并两个有序链表，要求使用原有链表中的节点，所以只需要依次比较大小，改变原有节点的指向。 代码如下

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        ListNode *head = new ListNode(0), *l;
        l = head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                l->next = l1;
                l1 = l1->next;
            }
            else {
                l->next = l2;
                l2 = l2->next;
            }
            l = l->next;
        }
        if (l1)
            l->next = l1;
        else if (l2)
            l->next = l2;
        return head->next;
    }
};

本代码提交AC，用时8MS。

二刷。循环的时候用或运算也可以，代码更简洁。

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		if (l1 == NULL)return l2;
		ListNode* ans = new ListNode(0);
		ListNode* root = ans;
		while (l1 || l2) {
			int v1 = l1 ? l1->val : INT_MAX;
			int v2 = l2 ? l2->val : INT_MAX;
			if (v1 != INT_MAX && v1 <= v2) {
				root->next = l1;
				root = root->next;
				l1 = l1->next;
			}
			else if (v2 != INT_MAX && v2 < v1) {
				root->next = l2;
				root = root->next;
				l2 = l2->next;
			}
		}
		return ans->next;
	}
};

本代码提交AC，用时8MS。