|
一个数组，“支配者”是在数组中出现频率超过一半的整数，
例如[3,4,3,2,-1,3,3,3]数值“3”出现过5次，5除以8大于0.5
所以数值“3”是一个支配者；
而在这个数组中的支配者出现在数组下标[0,2,4,6,7]
写一个函数，在给定的整数数组中找出支配者所在的任意一个数组下标，如果一个数组中没有支配者返回-1；
程序一：
import java.util.Arrays;
public class Test {
public static void main(String... strings) {
int[] arr = {3,4,3,2,-1,3,3,3};
int s = search(arr);
if(s == -1){
System.out.println("没有支配者！");
}else{
System.out.println("支配者："+s);
System.out.println("支配者所在数组下标：");
for(int i = 0;i <arr.length;i++){
if(arr[i] == s){
System.out.print(i+" ");
}
}
}
}
public static int search(int[] a){
int count = 1;
int[] arr = new int[a.length];
for(int i=0;i <a.length;i++){
arr[i]=a[i];
}
Arrays.sort(arr);
for(int i=1;i <arr.length;i++){
if(arr[i] == arr[i-1]){
count++;
if(count>arr.length*0.5){
return arr[i-1];
}
}else{
count = 1;
}
}
return -1;
}
}
程序二：
public class Test {
public static void main(String[] args) {
int[] array = {3,4,3,2,-1,3,3,3};
List<Integer> list = search(array);
for(Integer i:list){
System.out.print(i+" ");
}
}
public static List<Integer> search(int[] array){
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for(int i=0;i<array.length;i++){
//添加出现者和其出现位置
if(map.containsKey(array[i])){
map.get(array[i]).add(i);
}else{
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(array[i], list);
}
}
for(Integer i:map.keySet()){
double percent = (double)map.get(i).size()/(double)array.length;
if(percent>0.5){
return map.get(i);
}
}
//如果一个数组中没有支配者返回-1
List<Integer> list = new ArrayList<Integer>();
list.add(-1);
return list;
}
}
package test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class settest {
private int[] ar={3,4,3,2,-1,3,3,3};
public Map<Integer,Integer> getarr(){
Map<Integer,Integer> mp=new HashMap<Integer,Integer>();
Map<Integer,Integer> rp=new HashMap<Integer,Integer>();
for(int i=0;i<ar.length;i++){
if(mp.containsKey(ar[i])){
mp.put(ar[i], (mp.get(ar[i]))+1);
}else{
mp.put(ar[i],1);
}
}
Iterator <Integer>it=mp.keySet().iterator();
while(it.hasNext()){
Integer v=it.next();
int count=mp.get(v);
if((float)count/ar.length>0.5){
for(int i=0;i<ar.length;i++){
if(ar[i]==v.intValue()){
rp.put(ar[i],i);
}
}
}
}
return rp;
}
public static void main(String[] args) throws IOException {
settest t=new settest();
Map m=t.getarr();
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
String os = reader.readLine();
Integer s=Integer.valueOf(os);
if(m.containsKey((s))){
System.out.println(m.get(s));
}else{
System.out.println("-1");
}
}
}
public class Test {
public static void main(String[] args) {
int[] arr = {3,4,3,2,-1,3,3,3};
show(arr);
}
public static void show(int[] arr){
int len=(arr.length+1)/2;
int ret=0;
for(int i=0;i <len;i++)
{
ret=countor(arr[i],arr);
if(ret==1 )
{
break;
}
}
if(ret==0)
{
System.out.print("-1");
}
}
public static int countor(int x,int[] arr)
{
int ret=0;
int arrlen=arr.length;
int c=0;
for(int i=0;i <arrlen;i++)
{
if(arr[i]==x)
{
c++;
}
if(c*2>arrlen)
{
for(int k=0;k <arrlen;k++)
{
if(arr[k]==x)
{
System.out.print(k+" ");
}
}
ret=1;
break;
}
}
return ret;
}
}
import java.util.*;
public class ArrayTest
{
public static void main(String[] args)
{
int []num={3,4,3,2,-1,3,3,3};
LinkedList ll=new LinkedList();
float temp;
int n=0;
for(int i=0;i<num.length-1;i++)
{
for(int j=i+1;j<num.length;j++)
{
if(num[i]==num[j])
{
ll.add(new Integer(num[j]));
//将数组中与a[i]相同的值添加到列表中,a[i]未包含,所以最终的个数要+1
}
}
temp=ll.size()+1; //求数组中相同值的个数，并转换为float型，方便下面的除法运算
ll.clear(); //清空列表
if(temp/num.length>0.5) //判断是否为支配者
{
System.out.println("该数组中的支配者为:"+num[i]+",下标为:");
for(int m=i;m<num.length;m++) //找到该支配者的下标
{
if(num[i]==num[m])
System.out.println(m);
}
n++; //判断支配者的个数,如果最终为0,则没有支配者
}
}
if(n==0)
{
System.out.println("该数组中没有支配者");
}
}
}
import java.util.*;
public class Search {
static int found = 0;
public static void main(String[] args) {
int[] a = {3,4,3,2,-1,3,3,3};
search(a);
}
private static void search(int[] a){
List<Integer> l = new ArrayList<Integer>();
for(int i=a.length-1; i>=0; i--){
for(int j=0; j<i; j++){
if(a[j]==a[i]){
found++;
l.add(Integer.valueOf(j));
}
}
if(found+1>a.length/2){
l.add(Integer.valueOf(i));
System.out.print("这个数是" + a[i] + "，找到了" + (found+1) + "次。次序是：");
for(int k=0; k<l.size(); k++){
System.out.print(" " + l.get(k));
}
break;
}else{
found = 0;
l.clear();
}
}
if(found == 0){
System.out.print("没有支配者！");
}
}
}
import java.util.*;
public class temp {
public static void main(String[] args) {
int[] array = { 1, 2, 7, 3, 3, 4, 4, 5, 6, 3, 2, 3, 3, 3, 3, 3, 3 };
System.out.println(FindMaster(array));
}
// 查找数组中的支持者，并返回其道次在数组中出的下标.算法复杂度O(n)
// 使用集合实现
static int FindMaster(int array[]) {
HashMap<Integer, Integer> counter = new HashMap<Integer, Integer>();
// 数组所有元素存入hashmap.并在存入时统时其个数
for (int e : array) {
Integer v = counter.get((Integer) e);
if (v == null)
counter.put(e, 1);
else
counter.put(e, v + 1);
}
Integer maxcounterK = 0;
Integer maxcounterV = 0;
// 寻找出现次数最多的元素值和其出现次数
for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
Integer entryV = entry.getValue();
if (maxcounterV < entryV) {
maxcounterV = entryV;
maxcounterK = entry.getKey();
}
}
// 查找支持者首次出现的下标
if (maxcounterV > array.length / 2)
for (int i = 0; i < array.length; i++)
if (array[i] == maxcounterK)
return i;
return -1;
}
}
import java.util.Arrays;
/*一个数组，“支配者”是在数组中出现频率超过一半的整数，
例如[3,4,3,2,-1,3,3,3]数值“3”出现过5次，5除以8大于0.5
所以数值“3”是一个支配者；
而在这个数组中的支配者出现在数组下标[0,2,4,6,7]
写一个函数，在给定的整数数组中找出支配者所在的任意一个数组下标，如果一个数组中没有支配者返回-1；*/
public class constorl {
public static void main(String[] arg){
constorl a = new constorl();
System.out.print(a.control());
}
public int control(){
int[] arr = {3,4,3,2,-1,3,3,3};
int[] arr2 = Arrays.copyOf(arr,arr.length);
int mid = arr.length/2;
int returnID =-1;
Arrays.sort(arr2);
/* 根据题意，如果说单个数值出现的次数要超过一半，那么如果存在，那么在
数组排序之后，这个数组一定是中间一个，或者说是中间一个的下一个。*/
int control = arr[mid];
returnID = this.researchcontrol(arr,arr2[mid]);
if(returnID==-1){
returnID=this.researchcontrol(arr, arr2[mid+1]);
}
return returnID+1;
}
//@求key值在arr中是否出现超过一半，如果超过，则返回最后一个值，如果出超过，则返回-1
private int researchcontrol(int[] arr,int key) {
int index = -1;
int count = 0;
for(int i=0;i<arr.length;i++){
if (arr[i]==key){
count++;
index = i;
}
}
if(count<(arr.length/2)){
index = -1;
}
return index;
}
}
import java.io.*;
import java.util.*;
public class T {
public static List<Integer> search(String[] array){
Map<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>>();
for(int i=0;i<array.length;i++){
if(map.containsKey(Integer.parseInt(array[i]))){
map.get(Integer.parseInt(array[i])).add(i);
}else{
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(Integer.parseInt(array[i]),list);
}
}
for(Integer i:map.keySet()){
double percent = (double)map.get(i).size()/(double)array.length;
if(percent>0.5){
return map.get(i);
}
}
List<Integer> list = new ArrayList<Integer>();
list.add(-1);
return list;
}
public static void main(String[] args) {
System.out.println("请输入整数");
BufferedReader buf = null;
buf = new BufferedReader(new InputStreamReader(System.in));
String line;
StringBuffer sb = new StringBuffer();
try {
while((line=buf.readLine()) != null && !line.equalsIgnoreCase("exit")){
sb.append(line).append(" ");
}
} catch (IOException e) {
System.out.println("输入有误，请重新输入");
return;
}
List<Integer> list = search(sb.toString().trim().split("\\s+"));
for(Integer i:list){
System.out.print(i+" ");
}
}
}
C# code
using System;
using System.Collections.Generic;
using System.Text;
namespace TestApp
{
class Program
{
static void Main(string[] args)
{
IList<int> list = GetNum(new System.Int32[] { 6, 1, 6, 1, 2, 10, 1, 1, 6, 1, 1, 1, 1, 6, 1, 6});
if (null != list)
{
foreach (System.Int32 item in list)
{
Console.Write(item);
}
}
else
{
Console.Write(-1);
}
Console.Read();
}
public static IList<System.Int32> GetNum(System.Int32[] num)
{
System.Int32 temp = 0;
List<System.Int32> list = null;
if (num.Length > 0)
{
Dictionary<System.Int32, System.Int32> count = null;
foreach (System.Int32 item in num)
{
System.Boolean flag = false;
if (null == count)
{
count = new Dictionary<System.Int32, System.Int32>();
}
foreach (KeyValuePair<System.Int32, System.Int32> kvp in count)
{
if (item == kvp.Key)
{
int i = kvp.Value + 1;
count.Remove(kvp.Key);
count.Add(item, i);
flag = true;
break;
}
}
if (!flag)
{
count.Add(item, 1);
}
}
foreach (KeyValuePair<System.Int32, System.Int32> kvp in count)
{
System.Double i = Convert.ToDouble(kvp.Value) / Convert.ToDouble(num.Length);
if (i > 0.5)
{
temp = kvp.Key;
break;
}
}
for (System.Int32 i = 0; i < num.Length; i++)
{
if (temp == num[i])
{
if (null == list)
{
list = new List<int>();
}
list.Add(i);
}
}
}
return list;
}
}
}
//利用购物车算法编写
public class ArrayObject {
private Integer value;
private Integer suffix;
public ArrayObject(Integer value,Integer suffix){
this.value = value;
this.suffix = suffix;
}
public Integer getSuffix() {
return suffix;
}
public void setSuffix(Integer suffix) {
this.suffix = suffix;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
}
实体类的Item:
import java.util.ArrayList;
import java.util.List;
public class ArrayObjectItem {
private ArrayObject obj;
private List list = new ArrayList();
private int no;
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public ArrayObjectItem(ArrayObject obj){
this.obj = obj;
this.no = 1;
list.add(obj.getSuffix());
}
public List getList() {
return list;
}
public void setList(List list) {
this.list = list;
}
public ArrayObject getObj() {
return obj;
}
public void setObj(ArrayObject obj) {
this.obj = obj;
}
public void addSuffix(Integer suffix){
list.add(suffix);
}
public void addNo(){
this.no++;
}
}
类似购物车的算法类计算下标：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class CountSuffixCar {
private Map map = new HashMap();
public void addArrayObject(ArrayObject obj){
if(map.containsKey(obj.getValue())){
ArrayObjectItem objItem = (ArrayObjectItem) map.get(obj.getValue());
objItem.addNo();
objItem.addSuffix(obj.getSuffix());
}
else{
map.put(obj.getValue(), new ArrayObjectItem(obj));
}
}
public List getArraySuffix(int[] array){
List list = null;
for(int i=0;i <array.length;i++){
ArrayObject obj = new ArrayObject(array[i],i);
this.addArrayObject(obj);
}
Iterator it = this.getMap().values().iterator();
while(it.hasNext()){
ArrayObjectItem objItem = (ArrayObjectItem) it.next();
float percent =(float) objItem.getNo()/(float)array.length;
if(percent>0.5){
list = objItem.getList();
break;
}
}
if(list == null){
list = new ArrayList();
list.add(-1);
}
return list;
}
public Map getMap() {
return map;
}
public void setMap(Map map) {
this.map = map;
}
}
最后测试类：
import java.util.List;
public class TestArrayCountCar {
public static void main(String[] args) {
int[] array = {3,4,3,2,-1,3,3,3};
CountSuffixCar car = new CountSuffixCar();
List list = car.getArraySuffix(array);
for(Object obj : list){
System.out.println(obj);
}
}
}
using System;
using System.Collections.Generic;
using System.Text;
namespace TestApp
{
class Program
{
static void Main(string[] args)
{
Console.Write(Getnum(new int[] { 6, 1, 3, 1, 6, 1, 5, 1, 9, 1, 1, 1, 3, 6, 1, 1 }));
Console.Write(Getnum(new int[] { 6, 1, 3, 1, 6, 1, 5, 1, 9, 1, 1, 1, 3, 6 }));
Console.Read();
}
///
/// 查找数组中出现频率超过50%的那个数的所有下标，随机返回一个下标，无则返回-1
///
/// 传入的数组
/// 返回下标或-1
public static int Getnum(int[] num)
{
int k = -1;
if (num.Length > 0)
{
Dictionary<int, IList<int>> count = new Dictionary<int, IList<int>>();//实例化Dictionary
for (int i = 0; i < num.Length; i++ )//遍历数组
{
bool flag = false;//定义布尔值
foreach (KeyValuePair<int, IList<int>> kvp in count)//遍历当前Dictionary对象
{
if (num[i] == kvp.Key)//如果当前数组下标下的值已经存在
{
kvp.Value.Add(i);//将下标放入与当前Key值对应的IList对象中
flag = true;//修改bool值为true
break;//中断循环
}
}
if (!flag)//如果为false
{
IList<int> list = new List<int>();//实例化IList对象
list.Add(i);//添加当前下标
count.Add(num[i], list);//Key存放当前下标值到，Value存放IList对象
}
}
foreach (KeyValuePair<int, IList<int>> kvp in count)//遍历Dictionary对象
{
if ((Convert.ToDouble(kvp.Value.Count) / num.Length) > 0.5)//如果超过50%
{
Random ra = new Random();//实例化Random对象
k = kvp.Value[ra.Next(0, kvp.Value.Count)];//随机读取当前Ilist对象中的下标
break;//中断循环
}
}
}
return k;
}
}
}
|
