Java 面接でよくある配列に関する質問のまとめ (4)

对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5

/** *在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。 * 输入一个数组，求出这个数组中的逆序对的总数 P。 * 并将 P 对 1000000007 取模的结果输出。 即输出 P%1000000007 * * 利用归并排序的思想(倒序) * 当得到left和right两个待归并的数组时，由于二者已经排好顺序 * 当left中的A元素大于right中的B元素， * 那么right.length-b_index 个逆序对 * */ int count; public int InversePairs(int [] array) { return Merge(array,0,array.length-1); } public int Merge(int[] a, int start, int end) { if (start >= end) return count; int i,j,mid,index; int[] temp; mid = (start + end) / 2; Merge(a,start,mid); Merge(a,mid+1,end); i = start; j = mid + 1; temp = new int[end-start+1]; index = 0; while (i<=mid && j<=end) { if (a[i] > a[j]) { count = (count +end - j + 1) % 1000000007; temp[index++] = a[i++]; } else { temp[index++] = a[j++]; } } while (i<=mid) temp[index++] = a[i++]; while (j<=end) temp[index++] = a[j++]; index = start; for (i=0;i
        

         ログイン後にコピー
        
       

/** * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。 * 请写程序找出这两个只出现一次的数字。 * * 位运算中异或的性质： * 两个相同数字异或 = 0，一个数和 0 异或还是它本身。 * a ⊕ a = 0 * a ⊕ b ⊕ a = b. * a ⊕ 0 = a * * 当只有一个数出现一次时，我们把数组中所有的数，依次异或运算， * 最后剩下的就是落单的数，因为成对儿出现的都抵消了。 * * 当出现两个数只出现一次时，依旧是依次异或运算， * 剩下的结果是两个只出现一次的数的异或结果 * 因为这两个数不同，所以我们通过二进制的异或把二者分开，在依次异或即可分别得到 * */ public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { int i,n,res,count,res1,res2; n = array.length; if (n == 0 || array == null) return; res = 0;// 记录两个不同的数的异或结果 for (i=0; i
        

         ログイン後にコピー
        
       

/** * 输入一个递增排序的数组和一个数字 S， * 在数组中查找两个数，使得他们的和正好是 S， * 如果有多对数字的和等于 S，输出两个数的乘积最小的。 * */ public ArrayList FindNumbersWithSum(int [] array, int sum) { int mid,i,index,n,j; ArrayList list; n = array.length; if (n == 0 || array == null || sum == 0) return new ArrayList<>(); mid = sum >> 1; if (array[0] > mid) return new ArrayList<>(); // 前两个元素和为sum list = new ArrayList<>(); if (array[0] == mid) { if (array[0] + array[1] == sum) { list.add(array[0]); list.add(array[1]); } return list; } // 获得mid在array的索引 index = 0; for (i=0; i= mid) { index = i; break; } } i = 0; j = index + 1; while (i<=index) { while (array[i] + array[j] < sum) { j++; } if (array[i] + array[j] == sum) { list.add(array[i]); list.add(array[j]); break; } else { i++; j = index + 1; } } return list; }

/** * 输出所有和为S的连续正数序列。 * 序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序 * * 思路：回溯 * 算子，paths，path * */ TreeSet path; ArrayList> paths; ArrayList list; public ArrayList> FindContinuousSequence(int sum) { if (sum < 3) return new ArrayList<>(); int n,i,j,mid,count; paths = new ArrayList<>(); if (sum == 3) { list = new ArrayList<>(); list.add(1); list.add(2); paths.add(list); return paths; } // n代表sum这个数最多由几个数字构成 n = (int)Math.sqrt(sum) + 1; for (i=n; i>=2; i--) { count = 0; mid = sum / i; count += mid; path = new TreeSet<>(); path.add(mid); j = 1; while (count < sum) { count += mid+j; path.add(mid+j); count += mid-j; path.add(mid-j); j++; } if (count == sum) { list = new ArrayList<>(); list.addAll(path); paths.add(list); } else { int last = path.last(); int first = path.first(); if (count-last == sum) { path.remove(last); list = new ArrayList<>(); list.addAll(path); paths.add(list); } if (count-first == sum) { path.remove(first); list = new ArrayList<>(); list.addAll(path); paths.add(list); } } } return paths; }

/** * 判断顺子，大小王为0 * * 计算0的个数 * 计算非0的差 * */ public boolean isContinuous(int [] numbers) { if (numbers.length == 0 || numbers == null) return false; Arrays.sort(numbers); int n,i,count,minus; n = numbers.length; count = 0; minus = 0; for (i=0; i count ? false : true; }