题解 | #扑克牌顺子#
扑克牌顺子
http://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4
解法一:排序
在解决此题目之前,需要明确:在达到何种要求时,会实现「顺子」。
显而易见,当所抽取的非零牌存在重复时,不可能有顺子出现;此外,由于0可以代替任意牌,因此能否组成顺子是由「非零牌」决定的。故,此题的本质是要我们寻找非零牌之间是否满足一定的关系。
题目说明每次抽取牌的数量为5,因此若非零牌中的最大值与最小值之差小于5,则一定会组成顺子。
因此,题目转变成为:在非零牌中,寻找最大牌与最小牌,并计算其距离是否小于5。
解法一的思路如下:
- 将原数组排序(可利用C++内置的sort()方法进行排序);
- 可以得到数组中的最大数max(即有序数组的最后一个元素);
- 从头开始遍历排序好的数组:
- 若遇到0,跳过;
- 若遇到重复元素,返回false;
- 若max与当前值之差大于4,返回false;
- 循环结束时,比满足「最大值与最小值之差小于等于4」、「不存在重复元素」,因此直接返回true。
代码实现如下:
class Solution { public: bool IsContinuous( vector<int> numbers ) { if (!numbers.size()) return false; sort(numbers.begin(), numbers.end()); // 排序 int i = 0, max_ = numbers[numbers.size() - 1]; // 最大值为数组的最后一个元素 // 遍历数组 while (i < numbers.size() - 1) { // 跳过0 if (!numbers[i]) { i++; continue; } // 若有重复,返回false if (numbers[i] == numbers[i + 1]) return false; // 若最大与最小之差大于4,返回false if (max_ - numbers[i] > 4) return false; i++; } return true; } };
排序算法的平均时间复杂度为O(NlogN),遍历数组时间复杂度为O(N),因此总时间复杂度为O(NlogN)。
该方法未定义额外空间,空间复杂度为O(1)。
解法二:哈希表
可以优化上述方法的时间复杂度至O(N),即不采用排序算法。
如上文所述,题目转变成为:在非零牌中,寻找最大牌与最小牌,并计算其距离是否小于5。
因此,通过遍历原数组,并找出其最大值、最小值,即可解决此问题:预先定义变量min、max,分别代表最小值、最大值,并在遍历数组的过程中更新其取值,即可找到整个数组的最大、最小值(非0)。
此题需要注意重复元素的情况,因此引入哈希表便于判断:对于每一个遍历到的元素,在哈希表中进行寻找,若找到,说明有重复,否则将其加入哈希表中。
事例1:
事例2:
代码如下:
class Solution { public: bool IsContinuous( vector<int> numbers ) { int max_ = -1, min_ = 14; unordered_map<int, int> hash; // 定义哈希表 for (int i = 0; i < numbers.size(); i++) { if (numbers[i]) { // 跳过0 if (hash.find(numbers[i]) != hash.end()) // 若在哈希表中找到,说明有重复 return false; hash[numbers[i]] = 1; // 未在哈希表中找到,将其加入哈希表继续遍历 max_ = max(max_, numbers[i]); // 最大值 min_ = min(min_, numbers[i]); // 最小值 } } if (max_ - min_ <= 4) return true; return false; } };
此方法仅遍历数组一次,且哈希表的查找复杂度为O(1),故总时间复杂度为O(N);此方法定义了哈希表用来存储元素,因此空间复杂度为O(N)。