腾讯五十题 No.38 数组中第k个最大元素

题目链接
先用库函数试一下

快排：从两边往中间走，找个参照值，左边的大于参照值，右边的等于参照值时就交换这两个数。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        qsort(nums, 0, nums.length - 1);
        return nums[nums.length-k];
    }
    public void qsort(int[] nums, int l, int r) {
        if(l >= r) return;
        int i = l - 1, j = r + 1, x = nums[l + r >> 1];
        while(i < j){
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);
            if(i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        //用j做递归边界
        qsort(nums, l, j);
        qsort(nums, j + 1, r);
    }
}

推荐这些文章：

腾讯五十题 No.39 存在重复元素

题目链接
Set实现

Map实现
class Solution {
public boolean containsDuplicate(int[] nums) {
int len = nums.length;
Map<Integer,Integer> map = new HashMap<>(len);
for(int i = 0;i<len;i++){
if(map.containsKey(nums[i])){
return true;
...

腾讯五十题 No.36

题目链接

既然个数大于一般那就先sort,再取中间吧

但是面试官可能会想要其答案
class Solution {
public int majorityElement(int[] nums) {
int count = 1,maj = nums[0];
for(int i = 1;i < nums.length;i++){
if(maj==nums[i]){
count++;
}else{
count--;
...

腾讯五十题 No.44 除自身以外数组的乘积

题目链接

class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
int left = 1;
//让每个数等于自己左边所有数的乘积
for(int i = 0;i<n;i++){
ans[i] = left;
left *= nums[i];
}
int righ...

腾讯五十题 No.13 删除有序数组中的重复项

题目链接
class Solution {
public int removeDuplicates(int[] nums) {
int fast=1,slow=0;
while(fast<nums.length){
//如果快慢指针上的元素不相等就将该元素
if(nums[fast] != nums[slow]){
nums[slow+1] = nums[fast];
slow++;
}
...

腾讯五十题 No.16 全排列

题目链接
回溯+递归
0ms
class Solution {
public List<List<Integer>> permute(int[] nums) {

//1.初始化一个动态数组存储可能的数组
List<List<Integer>> res = new ArrayList<>();

//2.初始化一个用来记录元素是否被使用过的数组，如果被使用过就将元素对应在visited上的数组元素置为1
int[] visited = new int[nums....

腾讯五十题 No.29只出现一次的数字

不开辟新的空间，一般暗示用位运算或者异或解题

class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for(int num:nums){
single ^= num;
}
return single;
}
}

大神的一行解决
这个没上边的快
class Solution {
public int singleNumber(int[] nums) {
return Arrays...

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

常规解法（时空复杂度都是O(n）)

class Solution {
public int[] exchange(int[] nums) {
int[] b=new int[nums.length];
int k=0;
for(int i=0;i<nums.length;i++)
{
if(nums[i]%2==1)
{
b[k++]=nums[i];

}

}
...

腾讯五十题No.10 最接近的三数之和

题目链接
class Solution {
public int threeSumClosest(int[] nums, int target) {
int res = Integer.MAX_VALUE;
Arrays.sort(nums);
int sum = 0;
for(int i = 0;i<nums.length;i++){
if(i>0 && nums[i] == nums[i-1]) continue;
int l = i+1,r...

剑指 Offer 03. 数组中重复的数字

class Solution {
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);

for(int i=0;i<nums.length-1;i++){
if(nums[i]==nums[i+1]){
return nums[i];
}
}

return 0;

}
}

...

腾讯五十题No.16 最大子数组和

题目链接
class Solution {
public int maxSubArray(int[] nums) {
//sum每轮暂时存值，
int sum=0,res=nums[0];
for(int num:nums){
//sum为sum+下一个数组元素，与下一个数组元素之间的最大值
sum = Math.max(sum+num,num);
//
res = Math.max(res,sum);
}
r...