前言

一数组

数组特点：

内存连续，线性表结构
数组的插入操作

平均时间复杂度 O(n)

如果无序，则可以时间复杂度将为O(1)
数组删除操作

JVM 标记清除垃圾回收算法的核心思想

先将要删除的标记，然后统一删除

实现一个支持动态扩容的数组

// minCapacity 数组实际的新长度 
private void grow(int minCapacity) {
	 int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //数组原长度*1.5
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
 }
 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow 溢出
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
 }

实现一个大小固定的有序数组，支持动态增删改查

简书参考

LeetCode
实现两个数组合并为一个有序数组

leetcode 88号问题
两数之和

leetcode 1号问题

最简洁做法 hashMap一次遍历

//使用hashMap 两次遍历
/*
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
*/
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indexs=new int[2];
     	Map<Integer,Integer> map=new HashMap();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],i);
        }
        for(int j=0;j<nums.length;j++){
            int tmp=target-nums[j];
            if(map.containsKey(tmp)&& map.get(tmp)!=j){
                return new int{j,map.get(tmp)};
            }
        }       
    }
}

三数之和

leetcode 15号题

最优解使用对撞指针，同时在pre_num 和 next_num中去掉重复元素

class Solution {
     public List<List<Integer>> threeSum(int[] nums) {
          List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        int index=0;
        while (index<nums.length){
            if(nums[index]>0)
                break;
            int bindex=index+1;
            int cindex=nums.length-1;
                while (bindex<cindex){
                int tmp=nums[index]+nums[bindex]+nums[cindex];
                    if(tmp==0) {
                        res.add(Arrays.asList(nums[index],nums[bindex],nums[cindex]));
                        bindex=next_index(bindex,nums);
                        cindex=pre_index(cindex,nums);
                    }else if(tmp>0){
                        cindex=pre_index(cindex,nums);
                    }else {
                       bindex= next_index(bindex,nums);
                    }
                }
                index=next_index(index,nums);
            }
        return res;
    }
     private int next_index(int index,int[] nums){
        for (int i=index+1;i<nums.length;i++){
            if(nums[i]!=nums[index]){
                return i;
            }
        }
        return nums.length;
    }
    private int pre_index(int index,int[] nums){
        for (int i=index-1;i>0;i--){
            if(nums[i]!=nums[index]){
                return i;
            }
        }
        return -1;
    }
    
}

使用set去除重复元素，和对撞指针

class Solution {
     public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> set=new HashSet<>();
        Arrays.sort(nums);
        for (int i=0;i<nums.length-1;i++){
         int start=i+1;
         int end=nums.length-1;
         while (start<end){
             if(nums[i]+nums[start]+nums[end]==0){
                 set.add(Arrays.asList(nums[i],nums[start],nums[end]));
                 start++;
                 end--;
             }else if(nums[i]+nums[start]+nums[end]<0){
                 start++;
             }else {
                 end--;
             }
         }
        }
        return new ArrayList<>(set);
    }
    
}

众数之和

leetcode 第169号问题

  public int majorityElement(int[] nums) {
        Map<Integer,Integer> map=new HashMap();
        int max=nums[0];
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                int index=map.get(nums[i]);
                map.put(nums[i],++index);
                max=index-map.get(max)>0?nums[i]:max;
            }else{
                map.put(nums[i],1);
            }
        }
        return max;
    }

采用分治思想（不理解）

class Solution {
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }

        // recurse on left and right halves of this slice.
        int mid = (hi-lo)/2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid+1, hi);

        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }

        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length-1);
    }
}
442. 数组中重复的数据

数组中的第K个最大元素

leetcode 215

数组中重复的数据中等

leetcode 442

/*
关键点 把值当做索引 索引相同值相同 意味着 这个索引就是重复的
i=0 num=4 nums[4-1]=7--> -7  [4,3,2,-7,8,2,3,1]

i=1 num=3 nums[3-1]=2-->-2   [4,3,-2,-7,8,2,3,1]

i=2 num=-2 nums[2-1]=1--> -3  [4,-3,-2,-7,8,2,3,1]

i=3 num=7 nums[7-1]=3-->-3   [4,-3,-2,-7,8,2,-3,1]

i=4 num=8 nums[8-1]=1-->-1 [4,-3,-2,-7,8,2,-3,-1]

i=5 num=2 nums[2-1]=-3  存在 num=2

i=6 num=3 nums[3-1]=-2 存在num=3

i=7 num=1 nums[1-1]=4 -->-4 [-4,-3,-2,-7,8,2,-3,-1]
*/
   public List<Integer> findDuplicates(int[] nums) {
         List<Integer> list=new ArrayList<>();
        for (int i=0;i<nums.length;i++){
            int num=Math.abs(nums[i]);
            if(nums[num-1]>0){
                nums[num-1]*=-1;
            }else {
                list.add(num);
            }
        }
        return list;
    }

只出现一次的数字简单（异或解法）

leetcode 136

使用异或

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

数组中第K个最大元素中等

  PriorityQueue<Integer> queue=new PriorityQueue<>();
        for (int num:nums){
            if (queue.size()<k){
                queue.offer(num);
            }else if(queue.peek()<num){
                queue.poll();
                queue.offer(num);
            }
        }
        return queue.poll();

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

数组.md

数组.md

前言

一数组

LeetCode

Files

数组.md

Latest commit

History

数组.md

File metadata and controls

前言

一 数组

LeetCode

一数组