LeetCode Array

简介: LeetCode数组习题26.Remove Duplicates from Sorted Array题目描述:Given a sorted array, remove the duplicates in ...

LeetCode数组习题

26.Remove Duplicates from Sorted Array

题目描述:

Given a sorted array, 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 in place with constant mem- ory.
For example, Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

中文:

一个有序数组,返回不重复的元素的个数。

Java代码

 public  int removeDuplicates(int[] nums) {

     int index=0;
     for(int i=1;i<nums.length;++i){
        if (nums[i]!=nums[index]){
            index=index+1;
            nums[index]=nums[i];
         }
      }
      return index+1;
    }
时间复杂度 空间复杂度
O(n) O(1)

80. Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array 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. It doesn't matter what you leave beyond the new length.

Java代码

public int removeDuplicates(int[] nums) {
   int index=0;
   int occur=1;
   for(int i=1;i<nums.length;i++){
      if(nums[index]==nums[i]){
         if(occur<2){
             index=index+1;
             nums[index]=nums[i];
             occur++;
         }
      }else{
         index=index+1;
         nums[index]=nums[i];
         occur=1;
      }
   }
   return index+1;
}
时间复杂度 空间复杂度
O(n) O(1)

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

中文:

给定一个整型数组和一个目标值,返回和为目标值的2个数的位置。

解法一:冒泡排序思想遍历

 public  int[] twoSum(int[] nums, int target) {
        int[] index = new int[2];

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

            for (int j=i+1;j<nums.length;j++){
                if (nums[i] +nums[j]==target){
                    index[0]=i;
                    index[1]=j;
                    break;
                }
            }

        }
        return index;

    }
时间复杂度 空间复杂度
O(n^2) O(1)

解法二:使用HashMap

 public  int[] twoSum(int[] nums, int target) {
        int[] index = new int[2];

        HashMap<Integer,Integer> map=new HashMap<>();

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

            if (map.containsKey(target-nums[i])){
                index[0]=map.get(target-nums[i]);
                index[1]=i;
            }
            map.put(nums[i],i);
        }
        return index;

    }
时间复杂度 空间复杂度
O(n) O(n)

7. Reverse Integer

题目

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

中文:

整数逆序输出,超过32位无符号数的返回0.

Java代码:

public int inverse(int x) {
        long result = 0;
        while (x != 0) {
            result = result * 10 + x % 10;
            if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
                return 0;
            }
            x = x / 10;
        }
        return (int) result;
    }
时间复杂度 空间复杂度
O(n) O(1)

4. Median of Two Sorted Arrays

有序数组nums1和nums2长度分别为m和n,返回中位数。要求时间复杂度为O(log(m+n))。
例子1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

例子2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

先合并有序数组,再返回中位数,java代码如下:

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {


        int m=nums1.length;
        int n=nums2.length;
        int N=m+n;
        int[] nums=new int[N];
        int i=0,j=0,k=0;
        while (i<m&&j<n){
            if (nums1[i]<nums2[j]){
                nums[k++]=nums1[i++];
            }else{
                nums[k++]=nums2[j++];
            }
        }
        while (i<m) nums[k++]=nums1[i++];
        while (j<n) nums[k++]=nums2[j++];
        double  result=0;
        if (N%2!=0){
            result=(double) nums[N/2];
        }else{
            result =(double)(nums[N/2-1]+nums[N/2])/2;
        }
        return result;
    }
时间复杂度 空间复杂度
O(log(m+n)) O(log(m+n))

136. Single Number

给定一个整型数组,数组里的元素都出现2次,只有1个除外。找出只出现1次的元素:

解法一

Java代码:

    public int singleNumber(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int a:nums){
            if (map.containsKey(a)){
                map.remove(a);
            }else{
                map.put(a,1);
            }
        }

        return (int)map.keySet().toArray()[0];
    }

解法二

通过求与操作:

  public int singleNumber(int[] nums) {
        int n = nums.length;
        int goal=nums[0];
        for (int i=1;i<n;i++){
            goal^=nums[i];
        }

        return goal;
  }

189. Rotate Array

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

思路:三步反转法

java代码:

class Solution {

    public void rotate(int[] nums, int k) {
        k%=nums.length;
        reverseArr(nums,0,nums.length-1);
        reverseArr(nums,0,k-1);
        reverseArr(nums,k,nums.length-1);

    }

    public  void reverseArr(int[] nums,int from,int to){
        while(from<to){
            int temp=nums[from];
            nums[from]=nums[to];
            nums[to]=temp;
            from++;
            to--;
        }
    }


}

时间复杂度 空间复杂度
O(n) O(1)

《编程之法第二章》

2. 最小的k个数

目录
相关文章
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
45 0
|
算法 Python
LeetCode 410. Split Array Largest Sum
给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
142 0
LeetCode 410. Split Array Largest Sum
|
算法
LeetCode 330. Patching Array
给定一个已排序的正整数数组 nums,和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中,使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。
75 0
LeetCode 330. Patching Array
LeetCode 238. Product of Array Except Self
给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
83 0
LeetCode 238. Product of Array Except Self
LeetCode 189. Rotate Array
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
78 0
LeetCode 189. Rotate Array
|
算法
LeetCode Find Minimum in Rotated Sorted Array II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 注意数组中可能存在重复的元素。
84 0
LeetCode Find Minimum in Rotated Sorted Array II
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
|
算法 测试技术
LeetCode 88. 合并两个有序数组 Merge Sorted Array
LeetCode 88. 合并两个有序数组 Merge Sorted Array
|
人工智能 索引
LeetCode 1013. 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum
LeetCode 1013. 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum