C++LeetCode数据结构基础详解

一、只出现一次的数字

遍历一遍数组利用异或的特性来实现(相同为0,相异为1 )

例如[4,1,2,1,2] 4和1异或为5 5和2异或为7 7和1异或为6 6和2异或为4 这样就能找出唯一的数字了

public int singleNumber(int[] nums) {

int res=0;

for(int i=0;i<nums.length;i++){

res=res^nums[i];

}

return res;

}

二、多数元素

这题可以利用排序就返回中间位置元素,就是数量超过一半的数字,但是时间复杂度为O(nlogn),

利用摩尔投票法,实现遍历一遍数组就能找到多数元素,

具体实现:定义两个变量计数位和标记位,将计数位初始化为1 ,将标记位为数组第一个元素 如图[2,2,1,1,1,2,2]

在这里插入图片描述

public int majorityElement(int[] nums) {

//摩尔投票法 也叫同归于尽法

int count=1;

int res=nums[0];

for(int i=1;i<nums.length;i++){

if(res==nums[i]){

count++;

}else{

count--;

if(count==0){

res=nums[i];

count=1;

}

}

}

return res;

}

三、三数之和

三数之和有点类似与两数之和,但是难度确增加了不少

思路是先对数组进行排序,之后定义双指针**,左指针为i+1,右指针为最后一个数组元素,进行求和找和第一个数字相等的数**

在这里插入图片描述

public List<List<Integer>> threeSum(int[] nums) {

//排序加双指针

Arrays.sort(nums);

List <List<Integer>> list=new ArrayList<>();

if(nums==null||nums.length<3){

return list;

}

for(int i=0;i<nums.length-2;i++){

if(nums[i]>0){

break;

}

if(i>0&&nums[i]==nums[i-1]){//去掉重复元素

continue;

}

int left=i+1; int right=nums.length-1;

while(left<right){

int temp=-nums[i];

if(nums[left]+nums[right]==temp){

list.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));

left++;

right--;

while(left<right&&nums[left]==nums[left-1]) left++;

while(left<right&&nums[right]==nums[right+1]) right--;

}else if(nums[left]+nums[right]>temp){

right--;

}else{

left++;

}

}

}

return list;

}

注意:

1 .给数组排序之后判断元素是否大于0,大于直接返回,后面元素一定大于0

2. 去掉重复的元素,如果值相同继续指针移动

3. Arrays.asList() 是将数组转换成List集合的方法

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注的更多内容!

以上是 C++LeetCode数据结构基础详解 的全部内容, 来源链接: www.h5w3.com/246822.html

回到顶部