首页 > 其他分享 >2007. Find Original Array From Doubled Array

2007. Find Original Array From Doubled Array

时间:2022-09-18 10:11:07浏览次数:73  
标签:count int changed doubled Doubled original 2007 Array array

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

 

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

 

Constraints:

  • 1 <= changed.length <= 105
  • 0 <= changed[i] <= 105
 
    public int[] findOriginalArray(int[] A) {
        int n = A.length, i = 0;
        if (n % 2 == 1) return new int[0];
        int[] res = new int[n / 2];
        Map<Integer, Integer> count = new TreeMap<>();
        for (int a : A)
            count.put(a, count.getOrDefault(a, 0) + 1);
        for (int x : count.keySet()) {
            if (count.get(x) > count.getOrDefault(x + x, 0))
                return new int[0];
            for (int j = 0; j < count.get(x); ++j) {
                res[i++] = x;
                count.put(x + x, count.get(x + x) - 1);
            }
        }
        return res;
    }

https://leetcode.com/problems/find-original-array-from-doubled-array/discuss/1470959/JavaC%2B%2BPython-Match-from-the-Smallest-or-Biggest-100

标签:count,int,changed,doubled,Doubled,original,2007,Array,array
From: https://www.cnblogs.com/wentiliangkaihua/p/16704272.html

相关文章

  • Function pointer array
    #include<iostream>usingnamespacestd;doublesum(constdouble,constdouble);doubleproduct(constdouble,constdouble);doublesubtract(constdouble,c......
  • ArrayList 为什么线程不安全【转载】
    一、源码分析首先看看这个类所拥有的部分属性字段:1publicclassArrayList<E>extendsAbstractList<E>2implementsList<E>,RandomAccess,Cloneable,java.io.......
  • FormArray 调整数据位置
    getbeans(){returnthis.validateForm.get('beans')asFormArray;}change(fromIdx,toIdx){constformGroup=this.beans.at(fromIdx);this.beans.......
  • array.js 说明
    文件说明:数组操作集合引入代码:import$arrayfrom'@/common/js/array.js'varlists=['桌子','椅子','电视','空调','冰箱']//从数组中随机抽取二个元素varg......
  • Java 中的二维数组(2d array):一些细节
    二维数组长度char[][]paul=newchar[2][5];intn1=paul[1].length;System.out.println(n1);//5intn2=pa......
  • 16.判断JSON是JSONObject或者JSONArray
    JSONObjectjson=newJSONObject();Objectjson1=newJSONTokener(rrinfo.getParametersJson()).nextValue();if(json1instanceofJSONObject){json=JSONObject.parse......
  • [Google] LeetCode 2172 Maximum AND Sum of Array 状态压缩DP
    YouaregivenanintegerarraynumsoflengthnandanintegernumSlotssuchthat2*numSlots>=n.TherearenumSlotsslotsnumberedfrom1tonumSlots.You......
  • ArrayBuffer、Float32Array、Uint8Array 详解
    ArrayBufferArrayBuffer()是一个普通的JavaScript构造函数,可用于在内存中分配特定数量的字节空间。constbuf=newArrayBuffer(16);//在内存中分配16字节alert(......
  • 【做题笔记】CF1288C Two Arrays
    ProblemCF1288CTwoArrays题目大意:构造两个长度为\(m\),值域为\(n\)的序列\(a,b\),满足\(a\)单调不降,\(b\)单调不升,且\(\foralli\in[1,m],a_i\leb_i\),求合......
  • 【JS每日一题】Array.reduce函数
    题目题目来源于前端面试题宝典[[0,1],[2,3]].reduce((acc,cur)=>{returnacc.concat(cur)},[1,2])解析[1,2]会作为初始值首次放入到第一个参数......