• 只出现一次的数字
• 求众数
• 搜索二维矩阵 II

只出现一次的数字

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 :
输入: [2,2,1]
输出: 1

我的解答

先排个序，然后直接从头遍历找只出现了一次的。

class Solution {
public:
int singleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int>::iterator iter = nums.begin();
for (; iter != nums.end(); ) {
if (iter+1 == nums.end()) {
break;
}
else if (*iter==*(iter+1)) {
iter+=2;
}
else {
break;
}
}
return *iter;
}
};

别人的解答

用异或，相同的数字异或得到0.而落单的数字与0异或则是自己。

class Solution {
public int singleNumber(int[] nums) {
int num = 0;
for(int i = 0; i < nums.length; i++){
num = num ^ nums[i];
}
return num;
}
}

参考 https://blog.csdn.net/baidu_40931662/article/details/83892506

求众数

题目

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:
输入: [3,2,3]
输出: 3

我的解答

排个序，然后从头至尾遍历，找到出现次数>n/2的。

class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int>::iterator iter = nums.begin();
int result;
for (; iter != nums.end(); ) {
int num = 0;
int temp = *iter;
while (iter != nums.end() && *iter == temp) {
num++;
iter++;
}
if (num > nums.size()/2) {
result = temp;
}
}
return result;
}
};

别人的解答

摩尔投票法，这种方法是因为题目中说众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。所以设置一个计数器，选定第一个值作为起始值，然后后面的值如果是这个值那么计数加一，如果不等，那么计数减一，当计数器的值为零时，选取当前值作为新值继续计数。因为众数肯定大于1/2所以最后计数器不为零的数肯定是众数。

class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int num = nums[0];
for(int i = 0; i < nums.length; i++){
if(num == nums[i]){
count++;
}else{
count--;
if(count == 0){
num = nums[i];
count++;
}
}
}
return num;
}
}

参考 https://blog.csdn.net/qq_39032310/article/details/87473917

搜索二维矩阵 II

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。
  示例
  现有矩阵 matrix 如下：
  [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
  ]
  给定 target = 5，返回 true。
  给定 target = 20，返回 false。

我的解答

从左上角开始的话，往右往下都是比当前值大，不好控制搜索方向，所以从右上角开始搜索，若比当前值小则往左搜寻，若比当前值大则往下搜寻。

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int h = matrix.size();
if (h == 0) { // matrix为空的情况
return false;
}
int w = matrix[0].size();
int i = 0, j = w-1;
for (;i < h && j >= 0;) {
if (matrix[i][j] == target) {
return true;
}
else if (target < matrix[i][j]){
j--;
}
else {
i++;
}
}
return false;
}
};

题目

我的解答

别人的解答

最后

以上就是勤恳洋葱为你收集整理的【leetcode_2018高频算法题汇总】只出现一次的数字求众数搜索二维矩阵 II的全部内容，希望文章能够帮你解决【leetcode_2018高频算法题汇总】只出现一次的数字求众数搜索二维矩阵 II所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。